How Searching a Binary Search Tree Works

Q: Why do BST operations cost O(h) rather than O(log n)?

Because log n is only the height of a balanced tree. Insert values in sorted order and every node becomes a right child: the height is n, and searching is a linked-list scan. Height, not count, is what the cost depends on.

Q: A hash table looks up keys in O(1). Why use a BST at all?

For everything that needs order: ranges, predecessor and successor, the k-th smallest value, and iterating in sorted order. A hash table can do none of those, which is why database indexes are trees rather than hash maps.

Searching a binary search tree discards one subtree at every node, like binary search over pointers. Its cost is the tree's height — which is why the shape of the tree, not its size, is what matters.

Nodes comparedlooking for 55

Nothing yet.

Not reached
On the stack
Current
Visited

Speed

Step 1 of 3

Look for 55 in a balanced tree of 7 values, 3 levels deep.

Counters

Comparisons: 0
Result: -
Tree height: 3; 7 nodes
Worst case: 3; one compare per level

Settings

Looking for55How many values7

How it was built

Search

1node = root
2while node:
3 if target == node.value: return node
4 if target < node.value:
5 node = node.left
6 else:
7 node = node.right
8return NOT_FOUND

What each walk is for

Walk	What you get	Time	Extra space
In-order	Values in sorted order	O(n)	O(h)
Pre-order	Root before children, for copying a tree	O(n)	O(h)
Post-order	Children before root, for freeing or evaluating	O(n)	O(h)
Level-order	Shallowest nodes first, level by level	O(n)	O(w)
Search	One value, by comparing at each node	O(h)	O(1)

n is the number of values, h the height of the tree and w its widest level. Build the tree from sorted values and h grows all the way to n — that is what balancing prevents.

Complexity

Best	Average	Worst	Extra memory
O(1)	O(log n)	O(n)	O(1)

O(n) is not a corner case: inserting already sorted values builds a tree that is a linked list, and that is the single most common way a BST goes wrong.

How bst search works

Every node in a binary search tree splits the remaining values in two: smaller to the left, larger to the right. Searching compares the target with the node and follows one branch, discarding the other subtree entirely. Each step therefore costs one comparison and descends one level, so the total cost is the height of the tree — about log n if the tree is balanced, and n if it is a chain.

Start at the root.
If the node's value equals the target, it is found.
If the target is smaller, move to the left child; if larger, move to the right.
An empty child means the value is not in the tree — and that empty slot is where it would be inserted.

Implementation

The same algorithm the visualiser is running, written to be read.

def bst_search(root, target):
    node = root
    while node is not None:
        if node.value == target:
            return node
        # One comparison discards an entire subtree.
        node = node.left if target < node.value else node.right
    return None


def bst_insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = bst_insert(root.left, value)
    elif value > root.value:
        root.right = bst_insert(root.right, value)
    return root

When to use it

Use a BST when you need ordered operations as well as lookups: ranges, predecessors, successors, and in-order iteration. A hash table beats it for plain key lookups and cannot do any of those.
Use a self-balancing variant in production — red-black or AVL — because plain BSTs degrade to a list on sorted input and sorted input is extremely common.
Watch the height rather than the count: the visualiser's sorted-insert mode shows a tree of n nodes with height n, and searching it is a linear scan wearing a tree's clothes.

Check yourself

If the animation made sense, these should too.

Why do BST operations cost O(h) rather than O(log n)?