Searching in a BST

Searching is straightforward. The BST property tells you exactly which direction to go at each step.

The Algorithm

Search follows the same path as insertion:

1. Start at the root
2. Compare value with current node
3. If equal, found it
4. If smaller, go left
5. If larger, go right
6. If you reach null, not found

Recursive Implementation

Iterative Implementation

Iteration is often preferred for search since it’s simpler:

Try It Yourself

Use the interactive BST to search for values:

Insert some values first, then search for them. Notice how the search path follows the BST property.

Search Example

Let’s search for 40 in this tree:

    50
   /  \
  30   70
 / \  / \
20 40 60 80

1. Start at 50. 40 < 50, go left
2. At 30. 40 > 30, go right
3. At 40. 40 === 40, found it!

We only visited 3 nodes instead of checking all 7.

Returning the Node

Sometimes you want the node, not just true/false:

Time Complexity

• Average case: O(log n) - we follow one path from root to target
• Worst case: O(n) - if tree is unbalanced
• Best case: O(1) - if value is at root (rare)

This is much better than searching an unsorted array, which is always O(n).

Why BST Search is Fast

The BST property eliminates half the tree at each step. In a balanced tree with 1000 nodes:

• Array search: up to 1000 comparisons
• BST search: up to 10 comparisons (log₂(1000) ≈ 10)

That’s a huge difference.

What’s Next?

Searching is simple. Deletion is trickier because we need to maintain the BST property. Let’s tackle that next.