Trees· 10 min

BST Search

Find a value in O(log n) on balanced trees

Setup

Step 1 / 7

Current step

1 / 7

Search for 20 starting at root.

Step log

7 nodes · depth 3 · drag to pan, scroll to zoom
Current / on path
Just inserted
Found
bst_search.java
1Node search(Node root, int target) {
2    Node cur = root;
3    while (cur != null) {
4        if (cur.value == target) return cur;
5        cur = target < cur.value ? cur.left : cur.right;
6    }
7    return null;
8}
● Java

BST Search

At each node, compare the target with the node's value. Go left if smaller, right if larger. The BST property ensures O(log n) on balanced trees.

Nodes
7
Mode
search
Time (avg)
O(log n)
Time (worst)
O(n)
50307020406080
19 / 46