Sonith ManakkatMany things in computing are shaped like trees: folders inside folders, the structure of a web page, the choices in a game. A tree is a simple idea with a big payoff: if data is arranged the right way, you can find an item without looking at most of the others. This part starts with the family-tree picture, then meets two useful tree-based structures: the binary search tree and the heap. Each section has a plain layer first and an Expert view after it.
What a tree is
- RootThe single item at the top
- Parent and childA parent links down to its children
- LeafAn item with no children
- DepthHow many steps down from the root
Expert viewTrees as a data structure
A tree is a connected graph with no cycles. In a rooted tree, every node except the root has exactly one parent. The depth of a node is the number of edges from the root, and the height of the tree is the greatest depth. A binary tree allows at most two children per node, called left and right. The number of nodes at each level can at most double as you go down, so a binary tree holding n items can be as short as about log base 2 of n levels. That shortness is the source of the speed in the next section.
Binary search tree: ask one question per level
- Start at the rootThe root is 8
- Compare6 is smaller than 8, so go left
- Compare again6 is bigger than 4, so go right
- FoundThe item there is 6
Inserting works the same way: follow the left and right choices until you reach an empty spot, and hang the new item there.
- 1Is the target equal to this node?Yes Found it: stopNo keep going
- 2Is the target smaller than this node?Yes Go to the left childNo keep going
- 3OtherwiseGo to the right child. If there is no child there, the item is not in the tree
Takeaway. One comparison per level lets you ignore half of what remains.
Balanced tree
- Short and wide: about log n steps to reach any item
- Every question rules out about half the items
Lopsided tree
- Long like a chain: up to n steps
- Happens if items arrive already in order and nothing rebalances
Expert viewBalance and cost
Search, insert and delete on a binary search tree take time proportional to its height. When the tree is balanced the height is about log n, so these are O(log n). When it is lopsided, for example after inserting already sorted values into a plain tree, the height can reach n and the cost becomes O(n). Space is O(n).
Self-balancing variants exist that keep the height close to log n by rearranging the tree (called rotations) during inserts and deletes. Well-known families include AVL trees and red-black trees; I name them only as examples of the idea. Databases and file systems often use a related, wider kind of tree (a B-tree) that stores many items per node to reduce slow disk reads.
Walking a tree
Sometimes you want to visit every item, not find one. A tree walk (traversal) visits each node once. The usual recursive form for a binary tree has three versions that differ only in when the node itself is handled.
- In-orderLeft side, then the node, then right side
- Pre-orderThe node first, then left, then right
- Post-orderLeft, then right, then the node last
Expert viewTraversal notes
All three depth-first walks take O(n) time because each node is visited once, and use stack space proportional to the height (O(log n) when balanced, O(n) when lopsided). A level-order walk, visiting the tree one level at a time, uses a queue instead and is the same idea as breadth-first search from the graph part of this series. Pre-order is handy for copying a tree, post-order for deleting one safely (children before parents).
Priority queues and the hospital waiting room
Keeping a fully sorted list would work but is wasteful, since you only ever need the top item. A heap is a tree built for exactly this job. In a min-heap, every parent is smaller than or equal to its children, so the smallest item is always at the root. (A max-heap is the mirror image.) Note this is a weaker rule than a search tree: a heap does not keep left and right sides in order.
Show the 8 steps as text
- A min-heap: the smallest value always sits at the top. Insert values one by one.
- Insert 5: it is not smaller than its parent, so it stays.
- Insert 3: it swaps up 1 level because it is smaller than its parent.
- Insert 8: it is not smaller than its parent, so it stays.
- Insert 1: it swaps up 2 levels because it is smaller than its parent.
- Insert 4: it is not smaller than its parent, so it stays.
- Insert 2: it swaps up 1 level because it is smaller than its parent.
- Done: the smallest value, 1, is at the top, ready to be taken out first.
How a heap works
To insert, place the new item in the next free spot at the bottom, then compare it with its parent. If it is smaller, swap, and repeat. This "sifting up" stops quickly because the tree is short.
To extract the smallest, take the root, move the last item of the tree into the root's place, then "sift down": compare it with its two children and swap it with the smaller child, repeating until it is no larger than both children. The heap rule is restored.
- Take the rootIt is the smallest item
- Fill the gapMove the last item to the root
- Compare with childrenLook at the two below it
- Swap with the smaller childRepeat until the rule holds
Expert viewHeap in an array
A heap is a complete binary tree: every level is full except possibly the last, which fills from the left. That shape lets it live in a plain array with no pointers. With zero-based indexes, the node at index i has its parent at index (i - 1) / 2 (rounded down) and its children at 2i + 1 and 2i + 2.
| Operation | Time |
|---|---|
| Peek at the minimum | O(1) |
| Insert | O(log n) |
| Extract minimum | O(log n) |
| Build a heap from n items | O(n) |
| Search for an arbitrary value | O(n) |
Building from n items in O(n) uses a bottom-up method: sift down each non-leaf node starting from the last. Most nodes are near the bottom and move only a short way, which sums to linear work, better than n separate inserts at O(n log n). A heap does not support fast arbitrary search, which is why it is a priority queue and not a general lookup structure.
Where you meet them
- Priority schedulingPick the most urgent task next
- Shortest-path algorithmsOften use a priority queue to pick the next closest place
- Heap sortBuild a heap, then repeatedly extract the top
- Top-k questionsKeep the best k items seen so far with a small heap
- Files and foldersA directory tree is a general tree
- HTML structureElements nested inside elements form a tree
Try it by hand
On paper, insert 7, 3, 9, 1 into an empty binary search tree, in that order.
- Insert 7It becomes the root
- Insert 3Smaller than 7, so it goes left
- Insert 9Bigger than 7, so it goes right
- Insert 1Left of 7, then left of 3
- Walk in-orderRead left, node, right: 1, 3, 7, 9
Then try inserting 1, 3, 7, 9 in that order instead and see what shape you get.
A tree is fast when each step lets you ignore half of what is left.
Frequently asked questions
Is a heap the same as a binary search tree?
No. A heap only guarantees that each parent is smaller than its children, so it finds the minimum fast but cannot search for an arbitrary value fast.
Why does the order of insertion matter for a search tree?
Without rebalancing, sorted input produces a long chain, and searches become as slow as scanning a list.
Why store a heap in an array?
Its complete shape makes parents and children computable from the index, so no pointers are needed.
Are folders on a computer really a tree?
Yes. Each folder has one parent folder and can hold many children, which is the shape of a rooted tree.