BST Search - Learning Module

Loading content...

0/276

Algorithmic Steps

From Intuition to Implementation

Understanding why BST search works is essential, but building software requires translating that understanding into precise, executable steps. In this page, we dissect the BST search algorithm at the finest level of detail—every decision, every comparison, every pointer movement.

We'll present both iterative and recursive implementations, not as alternatives where one is "better," but as two lenses for understanding the same algorithm. The iterative approach makes state explicit and avoids stack usage; the recursive approach mirrors the tree's recursive structure and often leads to cleaner code.

By the end of this page, you'll be able to implement BST search correctly in any language, trace its execution on any tree, and identify subtle bugs that can creep into naive implementations.

What You Will Master

This page takes you from conceptual understanding to implementation mastery. You'll learn the precise algorithmic steps for BST search, implement both iterative and recursive versions, trace execution on sample trees, and understand the subtle differences between the two approaches.

The Algorithm in Pseudocode

Before diving into specific language implementations, let's express the BST search algorithm in clear pseudocode. This language-agnostic representation captures the essence of the algorithm.

Iterative BST Search:

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
function search(root, target):
    current ← root
    
    while current ≠ null:
        if target = current.value:
            return current          // Found! Return the node
        else if target < current.value:
            current ← current.left  // Go left
        else:
            current ← current.right // Go right
    
    return null  // Not found

Recursive BST Search:

pseudocode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function search(node, target):
    // Base case 1: Node is null (not found)
    if node = null:
        return null
    
    // Base case 2: Found the target
    if target = node.value:
        return node
    
    // Recursive case: Search in appropriate subtree
    if target < node.value:
        return search(node.left, target)
    else:
        return search(node.right, target)

Structural Analysis:

Both algorithms encode the same logic:

Check if current position is valid (not null)
Compare target with current value
If equal: We're done—return the node
If less: Continue in left subtree
If greater: Continue in right subtree
If null reached: Target doesn't exist—return null

The difference is purely mechanical: iterative uses a loop and updates a pointer; recursive uses function calls and lets the call stack track state.

Return Value Semantics

Notice that we return the node containing the target, not just a boolean. This is more flexible—the caller can check if the result is null (not found) or extract additional information from the found node. Some implementations return boolean or the value itself; choose based on your use case.

Iterative Implementation Deep Dive

The iterative approach uses a single pointer (current) that traverses from the root toward the leaves. Let's examine a complete, production-quality implementation.

bst_search_iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Searches for a value in a BST using iterative approach.
 * 
 * @param root - The root of the BST (may be null for empty tree)
 * @param target - The value to search for
 * @returns The node containing the target, or null if not found
 * 
 * Time Complexity: O(h) where h is the height of the tree
 * Space Complexity: O(1) - only uses a single pointer
 */
function searchBST(root: TreeNode | null, target: number): TreeNode | null {
    let current: TreeNode | null = root;
    
    // Traverse until we find target or reach null
    while (current !== null) {
        // Found the target
        if (target === current.val) {
            return current;
        }
        
        // Target is smaller - go left
        if (target < current.val) {
            current = current.left;
        } 
        // Target is larger - go right
        else {
            current = current.right;
        }
    }
    
    // Reached null without finding target
    return null;
}

Line-by-Line Analysis:

Line 17 (TS): Initialize current to the root. This is our traversal pointer.
Line 20: The while loop continues as long as current is not null. The null check is crucial—it prevents null pointer exceptions and signals unsuccessful search termination.
Lines 22-24: If we find our target, immediately return the node. No further traversal needed.
Lines 27-28: If target is smaller, move to the left child. This is justified by the BST property.
Lines 31-32: If target is larger, move to the right child.
Line 36: If the loop exits naturally (current became null), the target wasn't found.

Why Iterative is Often Preferred

The iterative approach is often preferred in production code because it uses O(1) extra space and cannot cause stack overflow, even for very deep trees. It's also slightly faster due to avoiding function call overhead. However, the recursive version's clarity makes it excellent for learning and prototyping.

Recursive Implementation Deep Dive

The recursive approach mirrors the tree's recursive structure: a tree is either empty (null) or a node with two subtrees. This structural correspondence leads to elegant, easy-to-reason-about code.

bst_search_recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
interface TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
}
 
/**
 * Searches for a value in a BST using recursive approach.
 * 
 * @param node - The current node (may be null)
 * @param target - The value to search for
 * @returns The node containing the target, or null if not found
 * 
 * Time Complexity: O(h) where h is the height of the tree
 * Space Complexity: O(h) - recursive call stack depth
 */
function searchBST(node: TreeNode | null, target: number): TreeNode | null {
    // Base case 1: Empty tree or reached leaf child
    if (node === null) {
        return null;
    }
    
    // Base case 2: Found the target
    if (target === node.val) {
        return node;
    }
    
    // Recursive case: Search in appropriate subtree
    if (target < node.val) {
        return searchBST(node.left, target);
    } else {
        return searchBST(node.right, target);
    }
}

Understanding the Recursive Structure:

The recursive implementation has exactly two base cases and two recursive cases:

Base Cases (recursion stops):

node === null: The subtree is empty, so the target isn't here → return null
target === node.val: We found it! → return the node

Recursive Cases (recursion continues):

target < node.val: Search left subtree → return searchBST(node.left, target)
target > node.val: Search right subtree → return searchBST(node.right, target)

The Call Stack Trace:

Let's trace searching for 40 in our example tree:

        50
       /  \
      30   70
     /  \    \
    20  40   80

searchBST(root, 40) called with node=50
- 40 ≠ 50, 40 < 50 → call searchBST(node.left, 40)
searchBST(node30, 40) called with node=30
- 40 ≠ 30, 40 > 30 → call searchBST(node.right, 40)
searchBST(node40, 40) called with node=40
- 40 === 40 → return node40
Return value propagates back:
- Call 3 returns node40 to call 2
- Call 2 returns node40 to call 1
- Call 1 returns node40 to caller

Call Stack at Maximum Depth:

│ searchBST(node40, 40) ← TOP (about to return)
│ searchBST(node30, 40)
│ searchBST(root, 40)   ← BOTTOM
└────────────────────────

Stack Overflow Risk

In a deeply unbalanced tree (e.g., 100,000 nodes in a straight line), the recursive approach creates 100,000 stack frames. Most languages have stack limits (often a few thousand frames), so this causes a stack overflow crash. For trees that might be unbalanced, use the iterative approach or ensure your language supports tail call optimization.

Step-by-Step Execution Trace

Let's trace the iterative algorithm with complete precision on a larger example. This kind of detailed tracing is essential for debugging and interview whiteboard problems.

Tree Structure:

            100
           /   \
         50     150
        /  \      \
       25   75    200
      /  \   \
     10  30   90

Example 1: Searching for 75 (successful search)

Trace: searchBST(root, 75)
Step	current.val	target	Comparison	Action	Next current
1	100	75	75 < 100	Go left	node(50)
2	50	75	75 > 50	Go right	node(75)
3	75	75	75 === 75	FOUND!	Return node(75)

Example 2: Searching for 85 (unsuccessful search)

Trace: searchBST(root, 85)
Step	current.val	target	Comparison	Action	Next current
1	100	85	85 < 100	Go left	node(50)
2	50	85	85 > 50	Go right	node(75)
3	75	85	85 > 75	Go right	node(90)
4	90	85	85 < 90	Go left	null
5	null	85	—	NOT FOUND	Return null

Analysis of the Trace:

Notice several important patterns:

Path Length: Successful search for 75 took 3 steps; unsuccessful search for 85 took 4 steps (plus the null check). The number of steps is bounded by the height of the tree.
Direction Changes: We can go left, then right, then left again. The path through the tree isn't necessarily monotonic in direction.
Failure at Leaf Edge: When searching for a non-existent value, we fail when we try to follow a child pointer that is null. This happens at the "edge" of the tree where the value would be inserted.

Tracing Practice

Drawing trees and tracing searches by hand is one of the best ways to build deep intuition. Practice tracing searches for the minimum value, maximum value, values near the root, and values that don't exist. Each scenario illuminates a different aspect of the algorithm.

Common Implementation Mistakes

Even experienced developers make subtle errors when implementing BST search. Let's examine the most common pitfalls and how to avoid them.

Mistake 1: Forgetting the Null Check

❌ Wrong
1
2
3
4
5
6
7
8
9
10
function searchBST(root, target) {
    // BUG: No null check!
    if (target === root.val) {
        return root;
    }
    if (target < root.val) {
        return searchBST(root.left, target);
    }
    return searchBST(root.right, target);
}

✅ Correct
1
2
3
4
5
6
7
8
9
10
11
12
13
function searchBST(root, target) {
    // Null check FIRST
    if (root === null) {
        return null;
    }
    if (target === root.val) {
        return root;
    }
    if (target < root.val) {
        return searchBST(root.left, target);
    }
    return searchBST(root.right, target);
}

The problem: Without the null check, calling root.val when root is null causes a crash. This happens when (a) the tree is empty, or (b) we've traversed past a leaf.

Mistake 2: Wrong Comparison Direction

❌ Wrong
1
2
3
4
5
6
// BUG: Directions reversed!
if (target < current.val) {
    current = current.right; // Should be left!
} else {
    current = current.left;  // Should be right!
}

✅ Correct
1
2
3
4
5
6
7
// target < current → go left
// target > current → go right
if (target < current.val) {
    current = current.left;
} else {
    current = current.right;
}

The problem: With reversed directions, the algorithm searches in the wrong subtree and never finds values that exist (or claims to find values that don't).

Mistake 3: Not Returning the Recursive Result

❌ Wrong
1
2
3
4
5
6
7
8
9
10
11
function searchBST(node, target) {
    if (node === null) return null;
    if (target === node.val) return node;
    
    if (target < node.val) {
        // BUG: No return statement!
        searchBST(node.left, target);
    } else {
        searchBST(node.right, target);
    }
}

✅ Correct
1
2
3
4
5
6
7
8
9
10
11
function searchBST(node, target) {
    if (node === null) return null;
    if (target === node.val) return node;
    
    if (target < node.val) {
        // Must RETURN the result!
        return searchBST(node.left, target);
    } else {
        return searchBST(node.right, target);
    }
}

The problem: Without return, the function computes the answer but doesn't propagate it back to the caller. The function always returns undefined (or None) unless the target is at the root.

Test These Edge Cases

Always test your BST search implementation with: (1) an empty tree, (2) a single-node tree, (3) target at the root, (4) target at a leaf, (5) target not in the tree, and (6) target smaller/larger than all nodes. These cases catch most implementation bugs.

Alternative Return Types

So far, we've returned the node itself when found (or null when not). Depending on your use case, other return types might be more appropriate.

Variant 1: Return Boolean (Existence Check)

bst_contains
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Checks if a value exists in the BST.
 * Use when you only need to know "is it there?" without getting the node.
 */
function contains(root: TreeNode | null, target: number): boolean {
    let current = root;
    
    while (current !== null) {
        if (target === current.val) {
            return true;  // Found
        }
        current = target < current.val ? current.left : current.right;
    }
    
    return false;  // Not found
}

Variant 2: Return Value (When Nodes Store Key-Value Pairs)

bst_get
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
interface TreeNode<K, V> {
    key: K;
    value: V;
    left: TreeNode<K, V> | null;
    right: TreeNode<K, V> | null;
}
 
/**
 * Retrieves the value associated with a key.
 * Returns undefined if key not found.
 * Used when BST is implementing a Map/Dictionary interface.
 */
function get<K extends number, V>(
    root: TreeNode<K, V> | null, 
    key: K
): V | undefined {
    let current = root;
    
    while (current !== null) {
        if (key === current.key) {
            return current.value;  // Return the associated value
        }
        current = key < current.key ? current.left : current.right;
    }
    
    return undefined;  // Key not found
}

Choose Based on Use Case

Return the node when callers need full node information. Return boolean for simple membership checks. Return the value when implementing a key-value map. All three use the same traversal logic—only the return value differs.

The Algorithm's Elegance

Step back and appreciate the elegance of BST search. With just a few lines of code, we achieve something remarkable:

Simplicity: The entire algorithm is expressible in ~10 lines of code. No complex data structures are needed beyond the tree itself.

Efficiency: Each comparison eliminates (ideally) half the remaining nodes. We achieve logarithmic search in a structure that supports dynamic updates.

Robustness: The algorithm handles all edge cases naturally—empty trees, single nodes, values not present—without special-case code.

Universality: The same algorithm works regardless of the tree's shape, the values stored, or the order in which nodes were inserted.

The Essence in One Sentence:

BST search follows a single path from root to target (or to null), making one comparison per level, guided by the invariant that the target can only be in the current subtree.

This sentence captures everything: the path, the comparisons, the invariant. Memorizing the algorithm is easy; understanding its essence is what makes you a master.

From Algorithm to Intuition

The goal isn't to memorize code but to internalize the pattern so deeply that you could recreate it from scratch in any language. When you truly understand BST search, you see it as the natural consequence of the BST property—the only sensible way to search an ordered tree.

Summary: Mastering the Algorithm

Let's consolidate the algorithmic steps we've mastered:

Key Takeaways

•Two equivalent implementations: Iterative uses a loop and pointer; recursive uses function calls and stack. Both encode the same logic.
•Three-way decision at each node: Equal (found), less than (go left), greater than (go right).
•Two termination conditions: Found the target (return node), or reached null (return null/false).
•Common mistakes to avoid: Always check for null first; use correct comparison directions; return recursive results.
•Return type flexibility: Return node, boolean, or value depending on use case.
•Iterative for production, recursive for clarity: Choose based on stack safety requirements and code readability needs.
•The algorithm is simple but deep: Mastery comes from understanding why each step exists, not just what it does.

What's Next:

Now that you can implement BST search flawlessly, we need to analyze its performance rigorously. The next page dives into time complexity analysis: why we say it's O(h), what h means exactly, and how this translates to O(log n) in the best case and O(n) in the worst case.

Understanding complexity is what separates programmers who can write code from engineers who can predict and optimize system behavior.

Page Complete

You now have complete command of the BST search algorithm—both iterative and recursive implementations, detailed execution traces, common pitfalls, and alternative return types. Next, we'll analyze the time complexity to understand exactly how fast (or slow) this algorithm can be.