Overview
Binary Search Tree search locates a key by exploiting the BST ordering: at each node it compares the target with the node's key and moves left if the target is smaller or right if it is larger, discarding half of the remaining tree at every step.
It is the tree analogue of binary search on a sorted array, following a single root-to-leaf path so the number of comparisons is bounded by the tree's height.
How BST Search works
- Start at the root node.
- Compare the target key with the current node's key; if they are equal, the search succeeds.
- If the target is smaller, move to the left child; if larger, move to the right child.
- Stop when the key is found or you reach a null link, which means the key is absent.
When to use it
- Fast membership tests and lookups in ordered in-memory data structures like sets and maps.
- Range queries and finding the closest key, since the ordering guides the path.
- The same comparison logic underlies BST insertion and deletion.
Complexity analysis
Each comparison moves one level down, so search costs O(h) where h is the tree height. A balanced BST keeps h at O(log n) for logarithmic search, but a degenerate, chain-like tree (e.g. built from sorted inserts) has h equal to n, degrading search to O(n). Space is O(1) iterative or O(h) recursive.
Frequently asked questions
Why can BST search degrade to O(n)?
If keys are inserted in sorted order the tree becomes a straight chain with height n, so a search may have to walk every node. Self-balancing trees such as AVL or Red-Black trees keep the height at O(log n) to prevent this.
How is BST search related to binary search on an array?
Both halve the search space per comparison. Binary search does it over a static sorted array, while a balanced BST does it over a dynamic structure that also supports efficient insertion and deletion.