Where it runs
1. The problem
You have a set of numbers that changes all day: new numbers keep arriving. You keep asking "is 42 in there?" and "give me all numbers from 10 to 20, in order". A sorted array searches fast by halving. But on every insert it has to shift all the items after the new one to make room. A hash set inserts and searches fast, but it has no order at all, so it can't answer the range question.
You need it all at once: fast search, fast insert and order, on a set that keeps changing.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedinsert(root, 4), insert(root, 13), insert(root, 6) // root = [8, 3, 10, 1, 6, null, 14]Every node splits its subtree: smaller values go left, larger go right. Insert [4, 13, 6] one by one.
Bars: the numbers in sorted order. The tree holds the same numbers, so a lit bar is the value the search just compared with the key.
One operation is one comparison. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n)O(log n)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- binary search tree: left < node < right at every node
- insert/delete/search while keeping the data ordered
- validate BST / kth smallest / inorder traversal gives sorted order
- closest value or range query on a set that changes over time
- no array given up front, values arrive one at a time
Looks similar, isn't
- Binary search (array)
An array halves by index but cannot take a cheap insert. A tree halves by pointer and can.
- Hash set / map
A map is faster for an exact lookup. A tree also answers ranges and gives sorted order.
- Binary heap / priority queue
A heap only promises the smallest value at the root. A search tree orders every pair of nodes.
- Tree traversal
That page is about visiting a whole tree. This one is about the ordering rule.
Balanced, n up to 1e6 gives O(log n) per operation. Unbalanced, the same tree degrades to O(n).
On LeetCode
Problems on a binary search tree where one comparison per node tells you which side to go. Search, insert and range questions walk one path, about log n steps when the tree is balanced.
The lesson's search, returning the node instead of true.
The lesson's insert under the same name.
Walk the tree and skip the left side when the node is below low, and the right side when it is above high.