Searching a BST & why balance matters

Search follows one path down — fast when balanced, slow when not. · 9 min read

Concept

Searching a BST is just the insert path without inserting: start at the root and go left if smaller, right if larger until you find the value or fall off the tree.

Interactive visualization: Insert & search follow a single root-to-leaf path — step through it frame by frame on this page.

Search invariant

At every node, the BST invariant lets you delete one whole side of the tree from consideration. If target < node->key, the target cannot be in the right subtree because every value there is even larger. If target > node->key, the target cannot be in the left subtree because every value there is smaller.

BST search invariant

look at one node — Compare target with the current key.
target is smaller — Only the left subtree can still contain it.
target is larger — Only the right subtree can still contain it.
target is equal — Search is finished.
child pointer is nullptr — The value is not present.

Result: One comparison discards an entire subtree

Worked example

Suppose the insertion order produced root 50, with 30 on the left and 70 on the right. Searching for 65 compares with 50 first, goes right, compares with 70, then goes left. The search never looks inside the entire left subtree of 50; those values are all too small. On a balanced tree, this pruning happens about log2(n) times.

C++ search code

struct Node {
    int key;
    Node* left;
    Node* right;
};

Node* search(Node* root, int target) {
    Node* cur = root;
    while (cur != nullptr) {
        if (target == cur->key) return cur;
        if (target < cur->key) cur = cur->left;
        else cur = cur->right;
    }
    return nullptr;
}

The iterative version uses O(1) extra space. A recursive version is shorter, but it uses call-stack space proportional to the height of the tree.

Time and space complexity

Because each step discards a whole subtree, the cost is the tree's height, O(h). A balanced tree has h ≈ log n, so search, insert and delete are all O(log n). The dedicated BST visualizer lets you insert and search your own values.

Practice: BST Search Path (Easy) — Trace the nodes visited while searching a BST.

Practice: Kth Smallest in a BST (Medium) — An in-order walk of a BST yields sorted order.

Practice: Lowest Common Ancestor in a BST (Hard) — Use the BST ordering to find the split point of two values.