CSC 378 tutorial: Searching in a Binary Search Tree

To search for a key k in a Binary Search Tree (BST), we start at the root node:

If k is less than the root's key, we descend to the left.
If k is greater than the root's key, we descend to the right.

Then we repeat the procedure from our new location and continue to descend through the tree. 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.

Example

To search in this BST, type a number in the box and press ``Enter.''

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. A tree is balanced if all root-to-leaf paths are short. Balanced trees are usually short and wide. We'll see balanced trees in the discussion on rotations.