We finally stop when either we find k in a node, or we can't go down any farther, in which case k is not in the tree. The nodes are highlighted as they are inspected during the search. The last node traversed is coloured green if the search was successful and red if it was not successful. If you were using a Java-enabled Web browser, you would see a binary search tree instead of this paragraph. Balanced trees Note that, in the worst case, a search will follow the longest path from the root to a leaf.
Balanced trees are usually short and wide.
We'll see balanced trees in the discussion on rotations. See also the BST property , BST rotations .