Algorithms from zero
Binary search trees
So far, you have walked trees, built them, measured their height. But search in a tree—any tree—requires walking every branch. A binary search tree changes that. It orders values: smaller on the left, larger on the right. This property lets you search by comparing, going left or right, never backtracking. Search becomes O(h). And since a balanced binary search tree has height O(log n), you search in logarithmic time.
After this lesson you can identify the BST property (left subtree smaller, right subtree larger), implement BST search and insertion, trace both operations to verify correctness, explain why in-order traversal of a BST yields sorted order, predict the time complexity of search and insertion (O(h) where h is height), and recognize the risk that an unbalanced tree can degenerate to O(n) height.
What is a binary search tree?
A binary search tree (BST) is a binary tree with a property: for every node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater than the node’s value.
This ordering invariant means the tree encodes a sorted order. It also means you can search by comparing: if you are looking for a value smaller than the current node, go left; if larger, go right. If equal, you found it. Since you never backtrack, searching is fast.
The BST property (left < node < right)
For each node:
- All values in the left subtree < node’s value.
- All values in the right subtree > node’s value.
- Both left and right subtrees are also BSTs (the property applies recursively).
Example:
5
/ \
3 8
/ \ / \
1 4 7 9Here, node 5 has left subtree 4 (all < 5) and right subtree 9 (all > 5). Node 3 has left subtree 1 (< 3) and right subtree 4 (> 3).
Search in a BST
To search for a value:
- Start at the root.
- Compare the target with the current node’s value.
- If equal, found it.
- If target is smaller, recurse on the left subtree.
- If target is larger, recurse on the right subtree.
- If you reach a null, the value is not in the tree.
At each step, you eliminate half the remaining tree (or a large part of it, if the tree is not perfectly balanced). This gives O(h) comparisons, where h is the height.
Insertion in a BST
To insert a value:
- Start at the root.
- Compare the value with the current node.
- If the value is smaller, recurse left; if larger, recurse right.
- When you reach a null, that is where you attach the new leaf.
Insertion also takes O(h) time because you must find the insertion spot by comparing at each level.
In-order traversal yields sorted order
In-order traversal (left, current, right) of a BST visits nodes in ascending order. This is because:
- You visit the left subtree (all values smaller than the node).
- Then the node itself.
- Then the right subtree (all values larger than the node).
So the values appear in sorted order.
Height is crucial
The search and insertion times depend on the height h:
- Balanced tree: height is O(log n), so operations are O(log n).
- Degenerate tree (e.g., all left children): height is O(n), so operations are O(n).
If you insert values in sorted order [1, 2, 3, 4, 5], the tree degenerates to a linked list, and you lose the logarithmic-time benefit. Self-balancing trees (AVL, red-black) maintain balance, but they are beyond this lesson.
Example 1: Searching for a value in a BST
1
function search(node, target) {
2
// Base case: value not found
3
if (node === null) return false;
4
5
// Check current node
6
if (node.value === target) return true;
7
8
// Recurse left if target is smaller
9
if (target < node.value) {
10
return search(node.left, target);
11
}
12
13
// Recurse right if target is larger
14
return search(node.right, target);
15
}
- L1 Search function: takes a node and a target value.
- L3 Base case: if node is null, the value was not found.
- L6 If the target equals the node's value, we found it.
- L9 If target is smaller, it can only be in the left subtree (BST property).
- L10 Recurse on the left subtree.
- L13 Otherwise, target must be larger, so recurse on the right subtree.
Example: Search for 4 in the tree:
5
/ \
3 8
/ \ / \
1 4 7 9- Start at 5. Target (4) < 5, go left.
- At 3. Target (4) > 3, go right.
- At 4. Target (4) == 4, return true.
Search took 3 comparisons.
Example 2: Inserting a value into a BST
1
function insert(node, value) {
2
// Base case: attach new node here
3
if (node === null) {
4
return new Node(value);
5
}
6
7
// Recurse left if value is smaller
8
if (value < node.value) {
9
node.left = insert(node.left, value);
10
}
11
// Recurse right if value is larger
12
else if (value > node.value) {
13
node.right = insert(node.right, value);
14
}
15
// Ignore duplicates (optional; some BSTs allow them)
16
17
return node;
18
}
- L1 Insert function: add a value into the tree rooted at node.
- L3 Base case: if node is null, create and return a new node with this value.
- L7 If value is smaller than the current node, it belongs in the left subtree.
- L8 Recursively insert into the left subtree and update the left child.
- L10 If value is larger, it belongs in the right subtree.
- L12 Recursively insert into the right subtree and update the right child.
- L16 Return the (possibly updated) node.
Example: Insert 6 into the tree:
5
/ \
3 8
/ \ / \
1 4 7 9- Start at 5. Value (6) > 5, go right.
- At 8. Value (6) < 8, go left.
- At 7. Value (6) < 7, go left.
- At null. Create new node with value 6.
Result:
5
/ \
3 8
/ \ / \
1 4 7 9
/
6Insertion also took 4 steps (comparisons + tree navigation).
Running search and insert on a concrete tree
1
let root = new Node(5, new Node(3, new Node(1), new Node(4)), new Node(8, new Node(7), new Node(9)));
2
search(root, 4);
1
let root = new Node(5, new Node(3, new Node(1), new Node(4)), new Node(8, new Node(7), new Node(9)));
2
insert(root, 6);
Time complexity: search and insert
Both search and insert operations traverse a path from the root to either a found node (search) or a leaf (insert). The number of comparisons equals the depth of that path, which is at most the height h of the tree.
- Best case (balanced tree): Height is O(log n), so both search and insert are O(log n).
- Average case (random insertions): Height is approximately O(log n), so both are O(log n).
- Worst case (degenerate tree): Height is O(n) (tree is a linked list), so both are O(n).
For the operations in this lesson’s code (search and insert), the time complexity is O(h), where h is the height.
Space complexity
Both search and insert use recursion, so the call stack depth is O(h). In-order traversal also uses O(h) recursion depth.
Which of these trees satisfies the BST property?
You search for value 6 in this BST. At each step, how many nodes do you compare?
What does in-order traversal of a BST produce?
A BST is built by inserting values in this order: [1, 2, 3, 4, 5]. What is the height of the resulting tree?
In the worst case (degenerate BST), what is the time complexity of searching for a value?
lesson.inset.undefined
Why BSTs? Unordered binary trees let you traverse, but not search efficiently. If you want to search without examining every node, you need structure: an ordering. The BST property gives you that structure. At each node, you know which subtree to explore, so you halve the problem (in a balanced tree) at each step.
lesson.inset.undefined
Degenerate BSTs. If you insert values in sorted order, the BST degenerates into a linked list. Height becomes O(n), and you lose the logarithmic benefit. This is why self-balancing trees (AVL, red-black) exist—they maintain balance. But for this lesson, just recognize that height matters.
lesson.inset.undefined
Confusing BST with sorted order guarantee. A BST does NOT guarantee that a standard tree traversal (like level-order) produces sorted order. Only in-order traversal produces sorted order. If you want to sort a sequence, you build a BST and in-order traverse it. But a BST is not primarily a sorting algorithm—it is a dynamic data structure for fast search.
What is the BST property and why does it enable fast search?
Binary search trees organize data with an ordering property: left subtree < node < right subtree. This property enables fast search and insertion in O(h) time, where h is the tree’s height. For a balanced tree, h is O(log n), making operations logarithmic. In-order traversal of a BST yields values in sorted order—a consequence of the ordering property. The critical caveat: if the tree is unbalanced (degenerate), height becomes O(n), and all operations degrade. Self-balancing trees (AVL, red-black) maintain balance automatically, but they are significantly more complex and beyond the scope of this lesson. The next lesson covers tree dynamic programming—techniques for solving recursive tree problems with memoization.