1. A method of operating a search engine device, comprising: evaluating a span prefix mask for a key residing at a leaf parent level of a search tree, maintained in a hierarchical memory of the search engine device, to identify a prefix match to an applied search key that resides at a leaf node of the search tree that is outside a search path of the search tree for the applied search key; and reading a bitmap associated with the leaf node from the memory to identify a pointer to associated data for the prefix match, said pointer having a value that is based on a position of a set bit within the bitmap that corresponds to a set bit within the span prefix mask that signifies the prefix match.