Overview
Curated: · Written: · Reviewed:
Trees
Tree problems reward a single habit: write the base case and the combination step, and let the recursive definition supply the traversal. This guide develops that habit across the three depth-first orders and level order, then turns to binary search trees — where the invariant constrains whole subtrees rather than immediate children, where every operation is bound by height rather than by node count, and where the logarithmic claim everyone quotes depends on a balance condition that sorted input destroys. It also covers the recurring shape of the harder problems, in which the recursion returns one value to its parent while recording a different answer globally, and is explicit about recursion depth on degenerate trees.
the tree as a recursive definition
A tree is a node whose children are trees, and almost every tree algorithm is that definition turned into code.
The recursive structure means an algorithm has exactly three parts: the base case for an absent node, the recursive calls on the children, and the combination of their results.
Base case, recurse, combine - three parts, in that order.
def size(node):
if not node: return 0 # base case
return 1 + size(node.left) + size(node.right) # combine the children
Interview trap. Writing tree code as an ad-hoc traversal with accumulated global state makes the base case implicit, which is where the null-handling defects come from.
Engineering practice. Write the base case first, then the combination, and let the recursion do the traversal.
height and depth
Depth is measured from the root down and height from the node up, and the two are routinely swapped in both directions.
Depth is known on the way down and can be passed as a parameter; height is known on the way up and must be returned from the recursion.
Depth is passed down; height is returned up.
def walk(node, depth=0):
if not node: return -1 # height of an absent subtree
print(node.val, "at depth", depth) # depth: known on the way down
h = 1 + max(walk(node.left, depth + 1), walk(node.right, depth + 1))
return h # height: known on the way up
Interview trap. Trying to compute height on the way down forces a second traversal per node, which turns a linear algorithm into a quadratic one.
Engineering practice. Pass depth down and return height up, and name the variable for whichever one it actually is.
the three depth-first orders
Preorder, inorder, and postorder differ only in when the node is visited relative to its subtrees, and each suits a different task.
Preorder visits before descending, which suits copying and serialisation; postorder visits after, which suits deletion and any computation depending on children; inorder is meaningful only for binary trees and yields sorted order on a search tree.
Ask whether the node's work needs its children's results.
| Order | Node visited | Suits |
|---|---|---|
| Preorder | before the subtrees | copying, serialising |
| Inorder | between them | sorted output from a search tree |
| Postorder | after them | deletion, subtree aggregates, heights |
Interview trap. Choosing an order by habit rather than by dependency produces code that reads a child's result before computing it.
Engineering practice. Ask whether the node's work depends on its children's results; if so it is postorder, and if the children's work depends on the node's, it is preorder.
breadth-first traversal
Level-order traversal uses a queue and visits nodes in order of depth.
Recording the queue's size at the start of each round separates the levels, which is what allows per-level aggregation without storing depths on the nodes.
Snapshot the queue length to separate the levels.
from collections import deque
q, out = deque([root]), []
while q:
level = []
for _ in range(len(q)): # the snapshot - taken before the loop mutates q
node = q.popleft()
level.append(node.val)
q.extend(c for c in (node.left, node.right) if c)
out.append(level)
Interview trap. Using a stack instead of a queue produces a depth-first order while looking like a level-order traversal.
Engineering practice. Snapshot the queue length per level, and reach for level order whenever the answer is per-level or the shallowest match.
the binary search tree invariant
In a binary search tree every key in the left subtree is smaller than the node and every key in the right subtree is larger — the constraint is over whole subtrees, not just the immediate children.
Validating the invariant therefore requires carrying a permitted range down the recursion, narrowing it at each step.
The constraint is over subtrees, so the check carries a range.
def valid(node, low=float("-inf"), high=float("inf")):
if not node: return True
if not low < node.val < high: return False
return valid(node.left, low, node.val) and valid(node.right, node.val, high)
# 5
# / \
# 1 6
# / \
# 4 7 <- 4 < 5 sits in the right subtree: invalid, though every parent looks fine
Interview trap. Checking only that each node lies between its two children accepts trees that violate the property one level further down.
Engineering practice. Validate with an inherited open interval, and test the classic counterexample where a deep right-subtree node is smaller than the root.
inorder traversal of a search tree
An inorder walk of a binary search tree yields its keys in sorted order, which is both a validation technique and a source of algorithms.
Because the walk is sorted, the kth smallest element, the successor of a node, and the validity of the tree all follow from a single traversal.
Stop at k rather than materialising the whole walk.
def kth_smallest(root, k):
stack, node = [], root
while stack or node:
while node: stack.append(node); node = node.left
node = stack.pop(); k -= 1
if k == 0: return node.val # early exit, O(h + k)
node = node.right
Interview trap. Materialising the entire sorted list to answer a kth-element query wastes linear memory when the walk can stop at k.
Engineering practice. Use a generator or an early return so the walk stops as soon as the answer is known.
search-tree operations are height-bound
Search, insert, and delete in a binary search tree cost O(h) where h is the height, which is logarithmic only when the tree is balanced.
Inserting sorted keys into an unbalanced tree produces a path, so every operation degrades to linear time while the code stays unchanged.
Sorted insertion makes a path: 1,000 nodes, height 1,000.
for v in range(1000): insert(root, v) # each new value goes right: a linked list
# search(999) now costs 1,000 comparisons, not 10.
Interview trap. Quoting logarithmic search-tree performance without the balance condition is the standard overclaim, and sorted input is the standard counterexample.
Engineering practice. Use a self-balancing tree from the standard library, and if writing one, state the balance invariant that gives the bound.
deletion with two children
Deleting a node with two children replaces it with its inorder successor or predecessor, which is the only replacement that preserves the ordering invariant.
The successor is the leftmost node of the right subtree, has at most one child, and can therefore be spliced out easily after its value is copied up.
Replace with the inorder successor: the leftmost node of the right subtree.
def delete(node, key):
...
succ = node.right
while succ.left: succ = succ.left # at most one child, by construction
node.val = succ.val
node.right = delete(node.right, succ.val)
Interview trap. Promoting an arbitrary child breaks the invariant for the entire subtree, and the corruption is not visible until a later search fails.
Engineering practice. Implement the successor-replacement case explicitly, and verify the ordering invariant over the whole tree after each deletion in tests.
balanced-tree families
AVL, red-black, and B-trees all guarantee logarithmic height, and they differ in how strictly they balance and therefore in what they optimise.
AVL keeps height differences within one, giving faster lookups and more rotations on write; red-black tolerates more imbalance for fewer rotations; B-trees widen each node to match a disk or cache line.
All logarithmic; they differ in what they optimise.
| Family | Balance rule | Optimises |
|---|---|---|
| AVL | heights differ by <= 1 | reads; more rotations on write |
| Red-black | no path more than 2x another | writes; fewer rotations |
| B-tree | wide nodes, uniform depth | disk and cache line size |
Interview trap. Treating them as interchangeable misses that the choice is a read-write trade-off, and that B-trees exist because of the memory hierarchy rather than the asymptotics.
Engineering practice. Use the standard library's ordered map, and know which family it is so its write cost is not a surprise.
rotations
A rotation changes a tree's shape while preserving its inorder sequence, which is why it can rebalance without breaking the search property.
It relinks three nodes and up to three subtrees in constant time, moving one child up and its parent down.
The inorder sequence is unchanged; only depths move.
y x
/ \ / \
x C <-> A y
/ \ / \
A B B C
Inorder is A x B y C on both sides - which is exactly why a rotation cannot break the search property.
Interview trap. Believing a rotation reorders the keys is a misunderstanding of what balance means; the sequence is invariant and only the depths change.
Engineering practice. Verify a rotation implementation by checking that the inorder walk is unchanged before and after.
the lowest common ancestor
The lowest common ancestor of two nodes is the deepest node having both in its subtrees, and in a search tree it is found by descending while both keys are on the same side.
In a general binary tree it is found by a postorder walk returning whether each subtree contains either target, with the ancestor being the node where the two reports meet.
On a search tree, descend while both keys are on the same side.
while root:
if p < root.val and q < root.val: root = root.left
elif p > root.val and q > root.val: root = root.right
else: return root # the split point, or one of the nodes itself
On a general binary tree this rule has no basis; use the postorder report-and-meet version.
Interview trap. Applying the search-tree descent to a general tree gives a wrong answer, because there is no ordering to decide the direction.
Engineering practice. Choose the algorithm from whether the tree is ordered, and handle the case where one node is an ancestor of the other.
path problems and return values
Many tree problems need a recursion that returns one thing to its parent while updating a different global answer.
In the maximum path-sum problem, each call returns the best downward path through the node, while the answer considers the path that turns at that node and cannot be extended upwards.
Return the best downward path; record the turning path separately.
best = float("-inf")
def gain(node):
global best
if not node: return 0
left, right = max(gain(node.left), 0), max(gain(node.right), 0)
best = max(best, node.val + left + right) # the path that turns here
return node.val + max(left, right) # what the parent may extend
Interview trap. Returning the turning path to the parent produces paths that visit a node twice and answers that are too large.
Engineering practice. Separate the returned value from the recorded answer explicitly, and write both meanings in a comment above the function.
serialisation and reconstruction
A binary tree can be reconstructed from a single traversal only if null children are recorded, or from two traversals that include inorder.
Preorder with explicit nulls determines the tree uniquely; preorder plus inorder does too, because inorder locates the root's split point.
Record nulls, or preorder alone is ambiguous.
# Both of these trees have preorder [1, 2]:
# 1 1
# / \
# 2 2
# With nulls: "1,2,#,#,#" and "1,#,2,#,#" - now unique.
Interview trap. Assuming preorder and postorder together suffice is wrong for general binary trees, since they cannot distinguish a single left child from a single right child.
Engineering practice. Record nulls when serialising, and when combining traversals, use the pair that includes inorder.
recursion depth on trees
Recursive traversal uses stack depth proportional to the tree's height, which is fine when balanced and fatal when degenerate.
A tree built from sorted input has height equal to its node count, so the recursion overflows on inputs that a balanced tree of the same size handles easily.
Depth is the height, and a degenerate tree's height is its node count.
root = build_sorted(range(10_000)) # height 10,000
inorder(root) # RecursionError at ~1,000
Interview trap. Testing on random trees never produces the degenerate shape, so the failure appears only on real, often sorted, data.
Engineering practice. Convert to an explicit stack when the tree's shape is not controlled, and test on a deliberately degenerate tree.
iterative traversal with an explicit stack
Every recursive traversal converts to an explicit stack, with the visit order determined by push order and by whether nodes are marked.
Preorder pushes the right child before the left; inorder pushes a chain of left descendants and pops to visit; postorder needs a visited marker or a reversed preorder.
Preorder pushes right before left so left pops first.
stack, out = [root], []
while stack:
node = stack.pop()
out.append(node.val)
if node.right: stack.append(node.right) # right first
if node.left: stack.append(node.left) # so left is on top
Interview trap. Writing an inorder loop by analogy with the preorder one visits nodes before their left subtrees.
Engineering practice. Implement inorder with the descend-then-pop pattern, and check the result against the recursive version on random trees.
the Morris traversal
A tree can be traversed in constant space by temporarily rewiring null right pointers to their inorder successors.
Each threaded link is created on the way down and removed on the way back, so the tree is restored by the end of the walk.
O(1) space by threading, at the cost of mutating the tree mid-walk.
while node:
if not node.left: visit(node); node = node.right
else:
pred = node.left
while pred.right and pred.right is not node: pred = pred.right
if not pred.right: pred.right = node; node = node.left # thread
else: pred.right = None; visit(node); node = node.right # unthread
Correct single-threaded; unsafe under a concurrent reader, because the tree is temporarily wrong.
Interview trap. The traversal mutates the tree during the walk, which makes it unsafe under concurrent readers even though it restores the structure afterwards.
Engineering practice. Reserve it for genuinely memory-constrained single-threaded contexts, and document the temporary mutation.
n-ary trees
Generalising to arbitrary child counts changes the code shape but not the reasoning: the base case, the recursion over children, and the combination remain.
Inorder loses its meaning without a left-right split, while pre- and postorder generalise directly by iterating the child list.
Iterate the child list; inorder has no meaning without a left-right split.
def preorder(node):
if not node: return []
out = [node.val]
for child in node.children: out += preorder(child) # all of them
return out
Interview trap. Porting binary-tree code by treating the first two children as left and right silently ignores the rest.
Engineering practice. Iterate the child collection, and reserve inorder for the binary case where it is defined.
trees versus hash structures
An ordered tree map costs a logarithmic factor over a hash map on point lookups and pays for it with ordered iteration and range queries.
Predecessor, successor, floor, ceiling, and range scans are all natural on a tree and impossible on a hash structure without a full scan.
The logarithm buys ordered queries a hash map cannot answer.
| Query | dict | ordered tree map |
|---|---|---|
| get(key) | O(1) expected | O(log n) |
| floor / ceiling of key | O(n) | O(log n) |
| keys in [lo, hi) | O(n) | O(log n + k) |
| iterate in order | sort first: O(n log n) | O(n) |
Interview trap. Choosing the hash map by default and then sorting for every range query is the common way this decision is made badly.
Engineering practice. Choose from the query mix, and pay the logarithm at write time if any read is ordered.
subtree aggregates
Storing an aggregate such as size or sum at each node turns several linear queries into logarithmic ones.
The aggregate is maintained on insertion and deletion along the modified path, so the extra cost is proportional to the height rather than to the tree.
Maintain the size on the modified path, or the rank query is a full walk.
def insert(node, v):
if not node: return Node(v, size=1)
node.size += 1 # updated along the path, O(h)
...
def rank(node, v): # how many keys are smaller
... # O(h) using node.left.size
Interview trap. Adding the field without updating it on every mutation path yields answers that are correct until the first deletion.
Engineering practice. Update aggregates inside the same functions that relink nodes, and assert them against a recomputation in tests.
balanced-tree guarantees in libraries
Standard-library ordered maps guarantee logarithmic operations, which is a contract worth relying on rather than reimplementing.
The implementations are red-black or B-tree variants with well-tested deletion, which is the part hand-written trees most often get wrong.
Deletion is the part hand-written trees get wrong.
# Python has no built-in ordered map; the practical choices are
# sortedcontainers.SortedDict - O(log n) with a well-tested implementation
# bisect over a list - O(log n) search, O(n) insert
# Java's TreeMap and C++'s std::map are red-black trees with the same guarantee.
Interview trap. Writing a balanced tree for production code is almost always a mistake unless the requirement is genuinely unusual.
Engineering practice. Use the library, and reserve a custom tree for augmented structures the library does not support.
tree diameter
The diameter is the longest path between any two nodes, and it is computed by a single postorder walk rather than by searching pairs.
At each node the candidate is the sum of the two tallest child heights, while the value returned upward is the single tallest — the same split between answer and return value as in path-sum problems.
The longest path need not pass through the root.
best = 0
def height(node):
global best
if not node: return 0
l, r = height(node.left), height(node.right)
best = max(best, l + r) # the path turning at this node
return 1 + max(l, r)
Interview trap. Assuming the diameter passes through the root is wrong for unbalanced trees, and the mistake produces answers that are too small.
Engineering practice. Track the best answer globally while returning the height, and test a tree whose diameter lies entirely inside one subtree.
checking structural properties
Symmetry, sameness, and subtree containment are all decided by a recursion over pairs of nodes rather than over a single node.
The recursion takes two nodes at once, so the base cases cover both being null, one being null, and values differing.
Recurse over pairs of nodes, not over one.
def mirror(a, b):
if not a and not b: return True
if not a or not b: return False
return a.val == b.val and mirror(a.left, b.right) and mirror(a.right, b.left)
Interview trap. Comparing serialised traversals is a common shortcut that gives false positives unless nulls are recorded.
Engineering practice. Recurse over node pairs, and if comparing serialisations, include explicit null markers.
the complete-tree array layout
A complete binary tree can be stored in an array with no pointers, where a node's children are at twice its index plus one and two.
This is the layout binary heaps use, and it makes traversal cache-friendly and memory overhead zero beyond the values themselves.
Children at 2i+1 and 2i+2; no pointers at all.
heap = [1, 3, 6, 5, 9, 8]
parent = lambda i: (i - 1) // 2
left, right = lambda i: 2 * i + 1, lambda i: 2 * i + 2
# For a sparse tree of height 20 this layout would need 2^21 slots for a handful of nodes.
Interview trap. Applying the layout to a sparse tree wastes memory exponential in the height, since absent nodes still occupy slots.
Engineering practice. Use the array layout only for complete or nearly complete trees, and switch to nodes when the shape is arbitrary.
complexity in terms of nodes and height
Tree complexities are stated in terms of n for traversals and h for root-to-leaf operations, and conflating the two hides the balance assumption.
A full traversal is always linear in n; a search is O(h), which is O(log n) only when balance is guaranteed.
O(h), and h is log n only when balance is guaranteed.
| Operation | Bound | Balanced | Degenerate |
|---|---|---|---|
| search / insert / delete | O(h) | O(log n) | O(n) |
| full traversal | O(n) | O(n) | O(n) |
Interview trap. Reporting a search-tree operation as O(log n) without saying the tree is balanced is the most common inaccuracy in this area.
Engineering practice. State the bound in h and then say what makes h logarithmic, which is exactly the balance invariant.
choosing a tree
A tree is the right structure when the data has a hierarchy, or when queries need order, range, or nearest-key answers.
Without an ordering requirement a hash structure is usually simpler and faster, and without a hierarchy the tree is an implementation detail rather than a model.
Name the ordered query, or a hash map is simpler and faster.
# Wrong reason: "the JSON is nested, so I need a tree."
# Right reason: "I need every event between two timestamps, in order."
Interview trap. Reaching for a tree because the data is nested in the source format confuses serialisation shape with access pattern.
Engineering practice. Name the query the tree answers that a flat structure cannot, and choose accordingly.