home
›
cheatsheets
›
computer_science
›
trees_heaps
Free to read Every card and diagram, and Quiz me
2
Free account Star cards. Your Quiz me marks are kept, so next time you drill just what you missed
3
Pro All 76 answers on this sheet, My sheet across every topic, and PDFs
A free account keeps your stars and Quiz me marks. Pro adds all 76 answers on this sheet, My sheet across every topic, and PDFs.
/
Read
Quiz me
Comfortable
Compact
0
Click any code to copy it
Done 0 /0
To review 0
On this sheet
01 Tree terms & shapes02 Traversals03 Binary search trees04 Balanced trees05 Binary heaps06 Priority queue patterns07 Tries08 Range queries09 Trees at scale10 Heaps at scale
The model A tree is nodes joined by edges, with one root and no cycles. Height is the number of edges on the longest path from the root to a leaf. Most operations cost O(height). A BST keeps smaller keys in a node's left subtree and larger keys in its right. A search drops one subtree per step, and an in-order walk reads the keys sorted. Balanced means the height stays near log n, so operations are O(log n). Sorted input turns a plain BST into a chain, and every operation becomes O(n). AVL and red-black trees rebalance to stop that.A heap is a complete tree stored in an array. In a min-heap no parent is larger than its children, so the min sits at the root. Peek is O(1), push and pop O(log n), search O(n). Use a hash map for exact keys, a BST for order and ranges, and a heap to keep taking the smallest or largest item. The same seven keys under two rules. The BST leads a search straight to any key. The heap only knows where its top is.
Tree terms & shapes the words and shapes every tree question uses Parts of a tree Name the parts of a tree One root on top. Every other node has one parent. A leaf has no children.
Tell a tree from a graph A tree is connected with no cycles, so n nodes have n-1 edges. A graph may have cycles.
Tell depth from height Depth counts edges up to the root. Height counts edges down to the deepest leaf.
Compute a tree's height const h = n => n ? 1 + Math.max(h(n.left), h(n.right)) : -1 An empty tree is -1, so a leaf is 0.
Trap Some books count nodes instead of edges, which adds one to both. Say which you mean.
Binary tree shapes Tell a binary tree from a general tree Each node has at most two children, left and right. A general tree allows any number.
Spot a full tree Every node has zero or two children.
Spot a complete tree Every level is full except the last, which fills from the left.
Spot a perfect tree Every level is full, so all leaves share one depth.
Tip Completeness is what lets a heap live in an array with no gaps.
Trap A complete tree need not be full, and a full tree need not be complete. A perfect tree is both.
Traversals visit every node in the order the job needs Pick a traversal order Copy or serialize a tree Pre-order. Node, then left, then right.
Read a BST's keys in sorted order In-order. Left, node, right. The BST rule puts each node between its subtrees.
Delete a tree or evaluate it bottom-up Post-order. Left, right, node. Children finish first.
Visit the tree row by row Level-order, a breadth-first walk with a queue.
Tip All four touch each node once, so each is O(n). Pick one for its order, not its speed.
Traversal memory and stack depth Estimate a depth-first walk's memory O(h), the path from the root. That's O(log n) balanced and O(n) on a chain.
Estimate a level-order walk's memory O(width). A balanced tree's last level holds about n/2 nodes.
Walk a deep, skewed tree safely Use an explicit stack instead of recursion, or keep the tree balanced.
Traverse with O(1) extra space Morris traversal. It briefly links each predecessor's empty right pointer to the node.
Tip Morris rewrites pointers as it runs, so it isn't safe with concurrent readers.
Trap Recursion passes tests on balanced trees, then overflows on sorted input. Python stops at 1000 frames.
Serialize a binary tree Write a tree to a string Pre-order, with a marker for each null. Root 1 with leaves 2 and 3 is 1 2 # # 3 # #.
Rebuild the tree from that string Read tokens in order. A marker is null. Otherwise make a node and recurse left, then right.
Trap Values alone are ambiguous. The null markers are what record the shape.
Binary search trees the ordering rule and every operation built on it The BST rule, search and insert State the BST rule Every key in the left subtree is smaller, and every key in the right is larger.
Search for a key while (n && n.val !== x) n = x < n.val ? n.left : n.right Each step drops a subtree. O(h).
Insert a key Search for it, then add a leaf where the search hit null.
Tip Pick a duplicate rule up front. Send equal keys right, or keep a count on the node.
Trap The rule covers whole subtrees. Every key anywhere left of 50 must be below 50, however deep it sits.
Min, max and successor Find the min or max while (n.left) n = n.left Leftmost is the min, rightmost the max.
Find the successor, given a right subtree The leftmost node in it. Step right once, then go left to the end.
Find the successor with no right subtree The lowest ancestor that has the node in its left subtree. Track your last left turn.
Delete a node 40 20 60 50 70 delete 40 40's successor is 50, the leftmost node on its right. Copy 50 up, then unlink the old 50.Delete a node with zero or one child Unlink a leaf. Splice a single child into the node's place.
Delete a node with two children Copy in its successor's key, then delete the successor from the right subtree.
Tip The successor is the right subtree's min, so it has no left child. Deleting it is the easy case.
Validate a BST function valid(n, lo = -Infinity, hi = Infinity) { if (!n) return true; if (n.val <= lo || n.val >= hi) return false; return valid(n.left, lo, n.val) && valid(n.right, n.val, hi); }
Check a whole tree in one pass Carry low and high bounds down. Keys must sit strictly inside, which rejects duplicates.
Check it with an in-order walk The keys must come out strictly increasing.
Tip Start the bounds at minus and plus infinity. A sentinel like the smallest integer fails on that value.
Trap Checking each node only against its children passes broken trees. A deep node can break an ancestor's bound.
Lowest common ancestor Find the LCA of two keys in a BST Walk down while both keys go the same way. Where they split is the LCA. O(h).
Find the LCA in a plain binary tree Recurse into both sides. Where the two targets first meet is the LCA. O(n).
Trap Both assume the two keys are in the tree. If one is missing, the BST walk returns a wrong ancestor.
BST or hash map Answer range, successor or sorted-order queries A BST. A hash map must scan all n keys and sort them.
Look up exact keys only A hash map. O(1) on average, but O(n) under bad collisions.
Balanced trees keep the height near log n, whatever order keys arrive in Why balance matters Search, insert or delete in a balanced BST O(log n). The height stays near log n.
Do the same in a plain BST built from sorted input O(n). Each key lands right of the last, so the tree is a chain.
Pick the best BST for a set of keys The shortest one. Insert order picks the shape, and n keys have a Catalan number of shapes.
Trap A plain BST looks fine on random keys and degrades on sorted or nearly sorted ones, which real feeds often are.
Rotations 10 20 30 before Sorted inserts leave a chain of height 2. Rotate left at 10, and 20 rises.20 10 30 after Height 1 now. An in-order walk still reads 10, 20, 30.Say what a rotation does It relinks a few nodes to shorten a tall side. The in-order sequence stays the same.
Repair an imbalance A single or double rotation at the unbalanced node. Deletes may repeat it up to the root.
AVL or red-black Pick a tree for read-heavy work AVL. Subtree heights differ by at most one, so it's shorter and lookups are faster.
Pick a tree for write-heavy work Red-black. Looser balance means fewer rotations per write.
State the red-black rules No red node has a red child. Every path down has the same number of black nodes.
Bound a red-black tree's height The longest path alternates red and black, so it's at most twice the shortest.
Tip Java's TreeMap is a red-black tree. Both kinds guarantee O(log n), and you rarely write either one.
Check and fix balance Check that a binary tree is height-balanced if (l < 0 || r < 0 || Math.abs(l - r) > 1) return -1 One post-order pass, O(n). This code counts an empty tree as 0, not -1, so -1 can flag imbalance.
Spot the slow version Recomputing height at every node costs O(n^2) on a skewed tree.
Rebuild a skewed BST with an array Read it in order, then make each middle key a root. O(n) time and space.
Rebuild it in place Day-Stout-Warren. Rotate it into a vine, then compress. O(n) time, O(1) space.
Tip Height-balanced means every node's two subtrees differ in height by at most one.
Treaps and skip lists Balance a tree with random numbers A treap. BST order on keys, heap order on random priorities. Expected height O(log n).
Pick a skip list over a balanced BST For concurrent ordered maps. Inserts never rotate. Redis sorted sets use one.
Trap Both are balanced only in expectation. A bad random source, or an attacker who learns it, can skew them.
Binary heaps a complete tree in an array, with the min or max on top The two heap rules State the shape rule Complete. Every level is full except the last, which fills from the left.
State the order rule In a min-heap no parent is larger than its children. A max-heap flips it.
Read the min or max h[0] O(1). It's always the root.
Tip The complete shape caps the height at about log n, which keeps push and pop at O(log n).
Trap A heap is not sorted. Its rule ties parents to children, never siblings to each other.
A heap in an array Find node i's children 2*i + 1 2*i + 2 Zero-based, level by level. Index math replaces pointers.
Find node i's parent (i - 1) >> 1
Trap One-based arrays use 2i and 2i + 1 instead. Mixing the two is the classic off-by-one.
Push and pop Push a value heapq.heappush(h, x) Append, then sift up while it beats its parent. O(log n).
Pop the top heapq.heappop(h) Move the last item to the root, then sift down via the smaller child. O(log n).
Trap On pop, promote the last item, never a child. Pulling a child up leaves a hole in the array.
Build a heap, and heapsort Build a heap from an array heapq.heapify(a) Sift down each parent, last to first. O(n).
Sort an array in place with a heap Build a max-heap, then swap the root to the end, shrink, sift down. O(n log n).
Say why heapsort is rarely used It misses the cache, so quicksort is 2 to 3 times faster. Introsort keeps it as a fallback.
Tip Heapify is O(n), not O(n log n). Half the nodes are leaves that never move, and most others sink a step or two.
Trap Heapsort isn't stable. Equal keys can come out in a different order than they went in.
What a heap can't do fast Search a heap for any value O(n). Siblings have no order, so no branch can be ruled out.
Find the max in a min-heap O(n). Any of about n/2 leaves could hold it.
Pick a balanced BST as a priority queue When you also delete any item, search or query ranges, each in O(log n).
Trap The last array slot isn't the max. For both ends fast, use two heaps or a min-max heap.
A max-heap from a min-heap Get max-heap order from a min-heap heapq.heappush(h, -x) x = -heapq.heappop(h) Negate on the way in and on the way out.
Use Python's own max-heap (3.14+) heapq.heappush_max(h, x) heapq.heappop_max(h)
Trap Negating the most negative fixed-width integer gives it back unchanged. Strings need a reversed comparator.
Priority queue patterns the heap problems interviewers ask you to code Priority queues Name a priority queue's operations Insert, peek at the top, and remove the top. Some also change a priority.
Pick a heap or a sorted list A heap if you insert and pop often. A sorted list if you need full order or the kth item.
Keep equal priorities in arrival order heapq.heappush(h, (prio, seq, item)) seq counts up, so ties pop in arrival order.
Trap A heap isn't stable. Equal priorities pop in any order unless you add a counter.
Top K and merge K Keep the K largest items of a stream if x > h[0]: heapq.heapreplace(h, x) A min-heap of size K. O(n log K) time and O(K) memory.
Merge K sorted lists A min-heap of list heads. Pop the smallest, push the next from its list. O(N log K).
Tip Store each value with its list's index, so you know which list to pull from next.
Trap A max-heap for the K largest makes you hold all n items. Use a min-heap capped at K.
Running median Track the median of a stream A max-heap for the low half, a min-heap for the high half. Keep sizes within one.
Read the median Odd count, the bigger top. Even count, the mean of both tops. O(1).
Trap Skip one rebalance and the tops stop bracketing the middle. The median goes wrong with no error.
Dijkstra and decrease-key Say why Dijkstra needs a priority queue It always expands the closest node. A binary heap gives O((V + E) log V).
Lower a distance without decrease-key Push a new entry and skip stale ones when they pop.
Change a priority in place An indexed priority queue. A map from item to heap index lets you sift it in O(log n).
Tip On a dense graph, where E nears V^2, a plain O(V^2) scan beats the heap.
Trap An indexed priority queue must update its map on every swap. One missed update corrupts it with no error.
Timers and schedulers Fire timers in deadline order A min-heap keyed by fire time. A worker sleeps until the root is due.
Cancel a timer Mark it dead and skip it on pop. Finding it costs O(n).
Hold millions of short-lived timers A hashed timer wheel. O(1) insert and expire over a bounded horizon.
Queue small integer priorities A bucket queue, one bucket per priority, or a calendar queue for event times. Insert is O(1).
Trap A new timer due before the root must wake the worker, or it sleeps past the deadline.
Tries prefix lookups on strings Trie lookups and memory Look up a key or a prefix O(L) for length L, however many keys there are. A prefix query collects one subtree.
Pick a hash map instead For exact keys only. It hashes once, while a trie chases a pointer per character.
Estimate a trie's memory It grows with the characters stored. Sparse nodes waste most of a 26-slot array.
Trap A million short keys can take hundreds of megabytes in a trie. A hash map would use a fraction of that.
Radix trees and autocomplete Shrink a trie A radix tree. It merges each chain of single-child nodes into one edge.
Serve autocomplete over millions of terms Store each node's top completions. Shard by prefix, and cache hot prefixes.
Trap A prefix trie can't match fuzzy or mid-word queries, and constant writes keep refreshing cached lists.
Range queries augmented trees for ranges, ranks and overlaps Range and rank queries Return every key between two bounds Seek the low bound, then walk in order. O(log n + k) for k matches.
Find the kth smallest key in O(log n) Store subtree sizes. Compare k with the left size to pick a side at each step.
Trap Every insert, delete and rotation must update the sizes. Miss one and ranks come back wrong with no error.
Interval and segment trees Find every interval that overlaps a query An interval tree, a BST on start points. Each node keeps its subtree's max end to prune.
Answer range sums or minimums with updates A segment tree. Queries and point updates both touch O(log n) nodes.
Tip Range updates on a segment tree need lazy propagation, or each one drifts toward O(n).
Trap An interval tree must recompute the max end up the path after every change, or its pruning drops real answers.
Trees at scale disks, caches, threads and old versions B-trees, B+ trees and the cache Say why databases use B-trees Each node fills a disk page with hundreds of keys, so a billion keys fit in 3 or 4 levels.
Scan a range in a B+ tree Descend once, then follow the linked leaves. The reads stay sequential.
Tell a B+ tree from a B-tree A B+ tree keeps every value in its leaves. A B-tree stores values in inner nodes too.
Say why a BST misses the cache Each node sits somewhere new in memory. A miss costs about 100 ns, 200 times an L1 hit.
Trap Size each node to the page. A mismatch wastes reads or splits a node across two pages.
Threads, versions and heavy writes Let readers skip locks Copy-on-write. Copy the changed path, then swap the root pointer atomically.
Keep every old version of a tree Path copying. Each update makes O(log n) new nodes and shares the rest.
Handle a write-heavy load Rotations dirty many nodes and contend near the root. LSM trees batch writes instead.
Trap You can't free an old node while a reader still holds it. Use RCU, hazard pointers or epochs.
Heaps at scale faster heaps, shared queues and data bigger than RAM Heaps beyond the binary heap Cut cache misses in a big heap A d-ary heap, d of 4 to 8. Siblings share a cache line and the tree is shallower.
Merge two heaps fast Leftist, skew, binomial or pairing heaps, in O(log n) or less. A binary heap needs O(n).
Speed up Dijkstra with a Fibonacci heap O(1) amortized decrease-key, O(E + V log V) total. Big constants lose in practice.
Trap Better big-O doesn't mean faster here. Pointer-based heaps miss the cache that a packed array hits.
Priority queues under load Share a priority queue across many threads Shard into sub-queues and pop the best visible head. You trade exact order for throughput.
Run a priority queue larger than memory Keep the active range in RAM, spill sorted runs to disk, and read in big sequential blocks.
Find the top K across a billion records Each shard keeps a local top K in a min-heap. A coordinator merges only those.
Trap Top K by frequency breaks the shard trick. One key's count splits across shards, so group keys first.
Nothing matches. Try a shorter word, or clear the search.
Practice Guided practice One question at a time, with the ones you miss coming back. Practice 76 interview questions Full answers, from beginner to expert.
Found this useful? Pass it on.
Share on LinkedIn
Share on X
Copy link
This sheet stays free. With Pro , you can:
Every answer on this sheet. Read the full answer to all 76 questions it links, not just the 11 free ones.My sheet. The cards you star and the ones you miss in Quiz me, from every sheet, on one page to quiz and print.PDFs. Download this sheet and My sheet, laid out for A4, with every question a link to its answer.The rest of Pro. Every answer in the question library, and 1,000 AI credits a month.
