Don't memorize the binary search tree — watch it grow. Every value that arrives goes left if it's smaller, right if it's larger, so the tree stays sorted without any extra work. Search then walks one path down, halving what's left at each step — O(log n). Until you feed it sorted input and it quietly collapses into a list.
insert · search · in-order · balancing
THE INVARIANT
Left subtree < node < right subtree, at every node.
SEARCH
Compare, go left or right — one path down, O(log n) when balanced.
IN-ORDER
Left, node, right → the values come out sorted.
THE CATCH
Sorted input builds a lopsided chain — O(n). Hence balancing.
Insert six values one at a time and watch the tree keep itself sorted. Press Step: each value walks down comparing — smaller goes left, larger goes right — until it finds an empty spot.
0
Nodes
—
Cost
Sorted by construction
The magic of a BST is that it never has to sort anything — the invariant does the work. Because left is always smaller and right always larger, both inserting a new value and searching for one become the same walk: start at the root, compare, and step left or right. Each step throws away a whole subtree, which is why a balanced tree answers in about log₂(n) steps.
01
Insert
Walk down comparing — smaller left, larger right — until you fall off the tree, and hang the new node there. O(log n) when balanced.
02
Search
The same walk: at each node go left or right. You either land on the value or run out of tree.
03
In-order traversal
Recurse left, visit the node, recurse right — the values come out in ascending order, for free, in O(n).
04
Balance it
Sorted input makes every node lean the same way — an O(n) chain. AVL and red-black trees rotate on insert to keep the height ~log n.
Search / Insert / Delete (balanced)
O(log n)
Worst case (degenerate)
O(n)
In-order traversal
O(n) sorted
Space
O(n)
Unlike a hash table, a BST keeps data ordered, so it answers range queries (“every value between 10 and 20”), successor/predecessor and min/max — things a hash table can't do. That ordered structure, kept balanced, is what powers database indexes (B-trees are the disk-friendly cousin) and language TreeMap/set types.
SOLVE IT YOURSELF
Solve it: BST in-order
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
Implement bst_inorder(vals): insert the values one by one into a binary search tree (smaller goes left, larger goes right), then return the in-order traversal as a list. Because of the BST ordering, that traversal comes out sorted. (Assume distinct values.)
HINTS — 4 IDEAS
A BST node holds a value plus left and right children. Insert by comparing: go left if the new value is smaller, right if larger.
Insert recursively: at an empty spot, create the node; otherwise recurse into the correct side and return the node.
In-order traversal visits left subtree → node → right subtree.
For a BST, in-order visits values in increasing order — that is why the result is sorted.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · In a BST, where does a value smaller than the current node go?
The invariant is left < node < right, so anything smaller than a node lives in its left subtree.
2 · Which traversal prints a BST's values in sorted order?
In-order visits everything smaller (left) before the node and everything larger (right) after — ascending order.
3 · What happens if you insert already-sorted values into a plain BST?
Every value goes the same direction, so the tree becomes a linked list of height n — the reason self-balancing trees exist.
Questions
BST vs hash table — which should I use?
A hash table gives O(1) average lookup but no order. A balanced BST gives O(log n) lookup and keeps keys sorted, so it supports range queries, ordered iteration, and min/max/successor. Use a hash table for pure key lookup; a tree when order matters.
What is a self-balancing tree?
A BST that rotates nodes on insert and delete to keep its height near log n, so operations stay O(log n) no matter the input order. AVL trees keep strict balance; red-black trees keep looser balance with fewer rotations; B-trees generalize the idea for disk and databases.
How do you delete a node with two children?
Replace it with its in-order successor (the smallest value in its right subtree) or predecessor, then delete that node — which has at most one child, an easy case. This preserves the BST invariant.
Ordered, and fast — while it's balanced.
Smaller left, larger right, search in O(log n), sorted for free. Just keep it from leaning.