The vocabulary of trees
A tree stores data hierarchically: a single root at the top, each node holding children below it, down to the leaves that have none. Unlike a list, a tree branches, and that branching is what buys speed.
Worth fixing the terms, because questions use them precisely: the height is the longest path from root to a leaf; the depth of a node is its distance from the root; a binary tree lets each node have at most two children.
Binary search trees: halving the problem
A binary search tree (BST) adds one rule: everything smaller than a node goes to its left, everything larger to its right. That single invariant means each comparison throws away half the remaining tree, giving O(log n) search, insertion and deletion — a million items in about twenty steps.
The catch: that speed assumes the tree stays bushy. Insert already-sorted data into a plain BST and every value goes the same way, so it degenerates into a linked list with O(n) search. The shape, not just the rule, is what matters.
Run In-order on this BST — the values come out perfectly sorted (10, 20, 25, 30…). That is the invariant made visible, and it is why an in-order walk is a free sort.
Keeping a tree balanced
Because a lopsided BST is slow, real systems use self-balancing trees — AVL trees and red-black trees. After each insertion they perform small local rotations that restore balance, guaranteeing the height stays around log n no matter what order the data arrives in.
You rarely implement these by hand, but you must know why they exist: they are the price paid to keep the O(log n) guarantee that a naive BST only offers on lucky input.
Balanced is the whole game
Every "O(log n)" claim about a tree quietly assumes it is balanced. AVL and red-black trees make that assumption safe; a plain BST does not. When an exam asks the worst case of a BST, the answer is O(n) — the unbalanced chain.
Heaps and priority queues
A heap is a different kind of binary tree with a weaker rule: every parent is smaller than its children (a min-heap) or larger (a max-heap). It does not keep things fully sorted — it only guarantees the smallest (or largest) sits at the root.
That is exactly what a priority queue needs: peek the most urgent item in O(1), and remove or add one in O(log n). Heaps power task schedulers, Dijkstra's algorithm, and heapsort. Neatly, a heap is stored in a plain array with no pointers at all: the children of index i live at 2i+1 and 2i+2.
| Structure | Search | Insert | Find min/max | Keeps sorted? |
|---|---|---|---|---|
| Balanced BST | O(log n) | O(log n) | O(log n) | yes (in-order) |
| Heap | O(n) | O(log n) | O(1) | no — only the extreme |
A worked example
Insert 50, 30, 70, 20, 40 into an empty BST, then say what an in-order traversal prints. Separately, what does a min-heap guarantee about its root?
- 50 is the root. 30 < 50 → left. 70 > 50 → right. 20 < 50 and < 30 → left of 30. 40 < 50 but > 30 → right of 30.Each value follows the smaller-left / larger-right rule from the root down.
- In-order (left, node, right) prints 20, 30, 40, 50, 70.In-order traversal of any BST emits its values in ascending order.
- A min-heap guarantees only that the root is the smallest value — the rest is not fully ordered.The heap rule is just parent ≤ children, enough to find the minimum instantly but not to list everything in order.
In-order gives 20, 30, 40, 50, 70; a min-heap guarantees the minimum is at the root (O(1) to read), nothing more.