Trees and Binary Search Trees Questions
Tree data structures as tested in coding interviews: binary trees, binary search trees, self-balancing trees (AVL insertion and deletion with rotations, a comparison with red-black trees, and alternatives such as treaps, splay trees and scapegoat trees), tries (prefix trees and radix trees), and N-ary, size-augmented and sum-augmented trees such as order-statistic trees. Covers traversal orders (in/pre/post-order, level-order, zigzag, iterative, generator-based and Morris variants), BST search, insertion and deletion invariants including duplicate-key policies, validation, successor and iterator design, range and kth-smallest queries, lowest common ancestor (including parent pointers, binary lifting and repeated queries on a static tree), tree reconstruction from traversals, serialization formats and parsing, converting between trees and sorted lists or linked lists, height, balance, diameter and path-sum recursion, subtree equality and hashing, persistent and snapshot-consistent trees, and how tree shape drives logarithmic versus degenerate performance. Excludes plain linked-list and stack/queue exercises with no tree in them, tree dynamic programming recurrences, general graph traversal, heap mechanics, and on-disk database index design, which are covered elsewhere.
What distinguishes a full, a perfect and a complete binary tree? For each, how would you check that a given tree has the property, and at what cost?
Sample Answer
The idea in plain words
All three words describe how "filled in" a binary tree (every node has at most two children) is, but they constrain different things. Two terms first: a leaf is a node with no children, and an internal node is any node with at least one child.
- Full: every node has either 0 or 2 children. Nothing has exactly one child. (Some textbooks call this property "strict" or "proper".)
- Perfect: every internal node has 2 children and all leaves sit at the same depth. Every level is completely filled.
- Complete: every level is completely filled except possibly the last, and the last level's nodes are packed as far left as possible, with no gaps. This is the shape a binary heap needs. A binary heap is a tree stored for a priority queue, where each parent is ordered against its children. A complete tree can be stored in a plain array, where slot
iis positionicounting from 0 (the root is slot 0), and the children of slotisit at slots2i+1and2i+2.
Textbooks differ a little on the names "full" and "complete", so say which definition you are using. Heights and depths here count edges (empty tree -1, single node 0).
How the three relate
- Every perfect tree is both full and complete.
- A full tree need not be complete (tree C below), and a complete tree need not be full (tree B below).
- A tree can be full and complete without being perfect: the 5-node tree with slots
[1, 2, 3, 4, 5]has a last level with only 2 of its 4 slots, packed on the left, and every node has 0 or 2 children.
Counting facts follow from the definitions:
- A perfect tree of height h has 1 + 2 + 4 + ... + 2^h = 2^(h+1) - 1 nodes.
- A full tree with i internal nodes has 2i child links, so n - 1 = 2i and n = 2i + 1: always an odd number of nodes, with i + 1 leaves.
- A complete tree with n nodes has height floor(log2 n) (log2 n rounded down). The reason: with height h, levels 0 to h-1 are full and hold 2^h - 1 nodes, and the last level holds between 1 and 2^h nodes, so n lies between 2^h and 2^(h+1) - 1, which is exactly the range where floor(log2 n) = h. The program prints the heights for 1 to 8 nodes next to floor(log2 n).
How to check each, and the cost
All three checks below are O(n) in time because a violation can be anywhere, so in the worst case every node is looked at once (the full and complete checks stop early at the first violation).
- Full: visit every node and test that it has either both children or none. Time O(n); the explicit stack holds about h + 1 entries, so O(h) space.
- Perfect: a tree of height h has at most 2^(h+1) - 1 nodes, with equality exactly when every level is full. So count nodes and measure height in one level-by-level pass, and compare
count == 2^(h+1) - 1. Time O(n), space O(width of the widest level), which is O(n) in the worst case. - Complete: walk breadth-first (level by level, left to right) and also queue the missing children as gaps. Once one gap is dequeued, every later item must also be a gap. A real node after a gap means the last level has a hole, or a lower level was left unfinished. Time O(n), and the queue holds up to about n + 1 items, so O(n) space.
Code
from collections import deque
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def from_slots(slots, i=0):
"""Build a tree from a heap-style slot list: children of slot i are slots 2i+1 and 2i+2.
None marks a missing node (its slots are ignored)."""
if i >= len(slots) or slots[i] is None:
return None
return Node(slots[i], from_slots(slots, 2 * i + 1), from_slots(slots, 2 * i + 2))
def draw(root):
"""Text drawing: the root on the first line, children below (left child first)."""
lines = [str(root.val)]
def walk(n, prefix):
kids = [c for c in (n.left, n.right) if c]
for j, c in enumerate(kids):
last = j == len(kids) - 1
tag = "L" if c is n.left else "R"
lines.append(prefix + ("`-- " if last else "|-- ") + f"{tag}:{c.val}")
walk(c, prefix + (" " if last else "| "))
walk(root, "")
return "\n".join(lines)
def is_full(root):
"""Every node has 0 or 2 children. One visit per node, explicit stack."""
stack = [root] if root else []
while stack:
n = stack.pop()
if (n.left is None) != (n.right is None):
return False
if n.left:
stack += [n.left, n.right]
return True
def size_and_height(root):
"""Node count and height in edges (empty tree -1, single node 0), by levels."""
count, height, level = 0, -1, [root] if root else []
while level:
count += len(level)
height += 1
level = [c for n in level for c in (n.left, n.right) if c]
return count, height
def is_perfect(root):
"""A tree of height h holds at most 2^(h+1) - 1 nodes, with equality exactly when every level is full."""
count, height = size_and_height(root)
return count == 2 ** (height + 1) - 1
def count_complete(root, steps):
"""Node count of a COMPLETE tree. steps[0] counts the links walked."""
if root is None:
return 0
left_height = right_height = 0
node = root
while node.left:
node, left_height = node.left, left_height + 1
steps[0] += 1
node = root
while node.right:
node, right_height = node.right, right_height + 1
steps[0] += 1
if left_height == right_height: # perfect subtree: use the formula
return 2 ** (left_height + 1) - 1
return 1 + count_complete(root.left, steps) + count_complete(root.right, steps)
def is_complete(root, log=None):
"""Breadth-first walk that also queues missing children. Once a gap (None) is seen,
any real node after it means a hole in the level order."""
queue, gap_seen = deque([root]), False
while queue:
n = queue.popleft()
if n is None:
gap_seen = True
if log is not None:
log.append(" dequeue gap")
continue
if log is not None:
log.append(f" dequeue {n.val}, gap_seen={gap_seen}")
if gap_seen:
return False
queue.append(n.left)
queue.append(n.right)
return True
if __name__ == "__main__":
examples = {
"A": [1, 2, 3, 4, 5, 6, 7],
"B": [1, 2, 3, 4, 5, 6],
"C": [1, 2, 3, None, None, 4, 5],
"D": [1, None, 2],
}
print(f"{'tree':<5}{'nodes':>6}{'height':>7}{'full':>7}{'perfect':>9}{'complete':>10}")
for name, slots in examples.items():
t = from_slots(slots)
n, h = size_and_height(t)
print(f"{name:<5}{n:>6}{h:>7}{str(is_full(t)):>7}{str(is_perfect(t)):>9}{str(is_complete(t)):>10}")
for name in "BC":
t = from_slots(examples[name])
print(f"\nTree {name}:")
print(draw(t))
log = []
print(f"is_complete -> {is_complete(t, log)}")
if name == "C":
print("\n".join(log))
# Height of a complete tree against floor(log2 n).
heights = [size_and_height(from_slots(list(range(1, n + 1))))[1] for n in range(1, 9)]
print("\nheights of complete trees with 1..8 nodes:", heights)
print("floor(log2 n) for n = 1..8: ", [n.bit_length() - 1 for n in range(1, 9)])
# Counting a complete tree without visiting every node.
steps = [0]
big = from_slots(list(range(1, 1001)))
print("count_complete on a 1000-node complete tree:", count_complete(big, steps), "| links walked:", steps[0])
# Empty tree and single node.
print("\nempty:", is_full(None), is_perfect(None), is_complete(None))
one = Node(1)
print("single:", is_full(one), is_perfect(one), is_complete(one))
Output:
tree nodes height full perfect complete
A 7 2 True True True
B 6 2 False False True
C 5 2 True False False
D 2 1 False False False
Tree B:
1
|-- L:2
| |-- L:4
| `-- R:5
`-- R:3
`-- L:6
is_complete -> True
Tree C:
1
|-- L:2
`-- R:3
|-- L:4
`-- R:5
is_complete -> False
dequeue 1, gap_seen=False
dequeue 2, gap_seen=False
dequeue 3, gap_seen=False
dequeue gap
dequeue gap
dequeue 4, gap_seen=True
heights of complete trees with 1..8 nodes: [0, 1, 1, 2, 2, 2, 2, 3]
floor(log2 n) for n = 1..8: [0, 1, 1, 2, 2, 2, 2, 3]
count_complete on a 1000-node complete tree: 1000 | links walked: 147
empty: True True True
single: True True True
Worked trace
The four trees are given as heap-style slot lists, where slot i has children in slots 2i+1 and 2i+2 and None marks a missing node.
- A
[1, 2, 3, 4, 5, 6, 7]is three full levels: full, perfect and complete, 7 nodes = 2^3 - 1. - B
[1, 2, 3, 4, 5, 6](drawn above) has node 3 with only a left child. Not full, so not perfect (6 is not 7). Complete: the queue yields 1 to 6 with no gap before them, then only gaps. - C
[1, 2, 3, None, None, 4, 5](drawn above) has every node with 0 or 2 children: full. Not complete: node 2 has no children, so two gaps are queued when it is processed. They are dequeued before node 4, and node 4 then arrives withgap_seen=True, which fails the check. It is not perfect either: 5 is not 7. - D
[1, None, 2]is a root with only a right child 2: not full, not perfect. Not complete either: the missing left child of 1 is a gap, and node 2 is dequeued after it.
The empty tree and a single node pass all three checks.
Edge cases and common mistakes
- Confusing "full" with "complete": C is full but not complete, B is complete but not full.
- Calling a perfect tree "just full". Perfect adds the equal-depth-leaves condition:
[1, 2, 3, 4, 5]is full and not perfect. - Checking only that every level above the last one is completely filled. C passes that test (its levels 0 and 1 are full), yet its last level has empty slots before real nodes: slots 3 and 4 are missing while 5 and 6 exist. The gap rule applied across the whole level order catches it.
- Testing "complete" by comparing left and right subtree heights. That is a balance test (it checks that the two subtree heights at every node differ by at most 1), a different property.
- Recursive versions on a deep tree: a recursive full check on a full tree more than about 1000 levels deep (every internal node has one leaf child and one deep child) raises
RecursionErrorin CPython, and so does a recursive height computation on a chain of 1500 nodes. The versions above are iterative.
Follow-ups and how the answer changes
- Complete check without a queue: give each node its slot index (
2i+1,2i+2) and require every index to be below n. Once n is known (counted with a loop), the recursion depth is bounded by about log2 n, because the slot index at least doubles each step down (a child of slotihas index at least2i+1), so a node k steps below the root has index at least 2^k - 1, and a tree whose indexes must all stay below n cannot be deeper than about log2 n. - Why heaps are stored as arrays: a complete tree has no gaps, so the slot formula never wastes space.
- Counting the nodes of a complete tree in less than O(n): walk down the left-most path and the right-most path from a node and compare their lengths. If they are equal, that subtree is perfect and its size is 2^(h+1) - 1 with no further visits. If not, count the node itself plus the two child subtrees the same way. In a complete tree at least one of the two child subtrees is perfect, so only one side keeps recursing: about h levels of recursion, each doing an O(h) walk, which is O(h^2) = O(log^2 n). The program's
count_completedoes this and prints the result: on a 1000-node complete tree it returns 1000 after walking 147 links, instead of visiting all 1000 nodes.
Running the code
# Python 3.12, standard library only
python tree_shapes.py
Given two BSTs, produce one sorted list of all their elements in O(m + n) time and O(h1 + h2) extra space. How would the same synchronized walk give the keys in one tree but not the other, or a merged balanced tree?
Sample Answer
The idea in plain words
An in-order traversal of a BST (binary search tree: left subtree keys smaller, right subtree keys larger) visits its keys in sorted order. So each tree is already a sorted sequence; the job is the merge step of merge sort, done on two trees without first copying them into arrays. The trick is to give each tree a lazy iterator (an object that produces the next item only when asked, instead of building the whole sequence first): an explicit stack that holds only the path from the root to the next unvisited node. Compare the two next keys, emit the smaller, advance that iterator. Heights here count edges (empty tree -1, single node 0), so a stack holds at most h + 1 nodes.
Brute force and why it is not enough
- Put every key in one list and call
sorted: O((m + n) log(m + n)) time and O(m + n) extra space, ignoring that both inputs are already sorted. - Flatten each tree into its own sorted list with an in-order walk, then merge the two lists: O(m + n) time but O(m + n) extra space for the temporary lists, which breaks the O(h1 + h2) bound.
- Insert every node of one tree into the other: O(n log(m + n)) for balanced trees, and not a sorted list at all.
Approach
- A
Walkerholds a stack. It starts by pushing the root and all its left descendants, so the top of the stack is the smallest key.next()pops that node, then pushes the left spine of its right child (the right child followed by its chain of left children, down to the smallest key there); each node is pushed once and popped once. mergeis a Python generator function (yieldhands one node to the caller and pauses until the next one is requested, so nothing is stored beyond the two walkers) and keeps oneWalkerper tree. While both have nodes, compare the tops and take the smaller. On equal keys it takes tree A first, so equal keys come out A before B.- When one walker is empty, drain the other (emit everything it still holds, in order, since all of it is larger than what was already emitted).
The same two walkers answer the other two questions:
- Keys in A but not in B (
difference, assuming each tree holds distinct keys): if A's key is smaller, it cannot be in B (everything left in B is larger), so emit it; if the keys are equal, drop both; if B's is smaller, drop B's. Intersection is the "equal" case. Nothing is emitted for B-only keys. - A merged balanced tree: you know the count m + n, and the merged keys arrive in sorted order, so
build_balancedbuilds the left half from the stream, takes the next key as the root, then builds the right half. No temporary list exists, and the recursion is only log2(m + n) deep. Why it is balanced: forcountkeys the left part getscount // 2keys and the right part gets the rest,count - count // 2 - 1, so at every node the two sides differ in size by at most one, and sizes that close give heights that differ by at most one. Thecountlines in the output show the splits: 12 keys become 6 + root + 5, then 6 becomes 3 + root + 2 and 5 becomes 2 + root + 2. Because the stream is read in sorted order and the left part is built first, the next key is always the one that belongs at the root of the part being built. With repeated keys the result obeys left <= key <= right, but not the "equal keys go right" rule thatinsertfollows: in the drawn tree the second 3 sits in the left subtree of the first 3, which theorder_rulesline in the output reports. No balanced tree can satisfy that stricter rule in general, since 15 equal keys under it must form a right chain; keep the stricter rule only by removing repeated keys first.
Code
import random
class Node:
def __init__(self, key, tag=None):
self.key, self.tag = key, tag
self.left = self.right = None
def insert(root, key, tag=None):
"""Plain BST insert (iterative). Equal keys go to the right."""
node = Node(key, tag)
if root is None:
return node
cur = root
while True:
side = "left" if key < cur.key else "right"
nxt = getattr(cur, side)
if nxt is None:
setattr(cur, side, node)
return root
cur = nxt
def height(t): # edges: empty tree -1, single node 0
return -1 if t is None else 1 + max(height(t.left), height(t.right))
class Walker:
"""In-order walk with an explicit stack: peek() shows the next node, next() consumes it."""
def __init__(self, root):
self.stack, self.peak = [], 0
self._push_left(root)
def _push_left(self, node):
while node:
self.stack.append(node)
node = node.left
self.peak = max(self.peak, len(self.stack))
def has(self):
return bool(self.stack)
def peek(self):
return self.stack[-1]
def next(self):
node = self.stack.pop()
self._push_left(node.right)
return node
def merge(t1, t2, ties_from_first=True, log=None):
"""Yield every node of both trees in sorted order, touching each once."""
a, b = Walker(t1), Walker(t2)
while a.has() and b.has():
take_b = b.peek().key < a.peek().key if ties_from_first else b.peek().key <= a.peek().key
src, name = (b, "B") if take_b else (a, "A")
node = src.next()
if log is not None:
log.append(f"take {node.key} from {name}; stack sizes now A={len(a.stack)} B={len(b.stack)}")
yield node
for src in (a, b):
while src.has():
yield src.next()
merge.peak = max(a.peak, b.peak)
def difference(t1, t2):
"""Keys in t1 that are not in t2 (each tree holds distinct keys)."""
a, b = Walker(t1), Walker(t2)
out = []
while a.has():
if not b.has() or a.peek().key < b.peek().key:
out.append(a.next().key)
elif a.peek().key == b.peek().key:
a.next()
b.next()
else:
b.next()
return out
def build_balanced(stream, count):
"""Build a height-balanced BST from `count` sorted keys read once from `stream`."""
if count == 0:
return None
left = build_balanced(stream, count // 2)
root = Node(next(stream))
root.left = left
root.right = build_balanced(stream, count - count // 2 - 1)
return root
def draw(t):
"""Text drawing; L and R mark which side each child hangs on."""
lines = []
def walk(n, label, prefix, last, top):
text = str(n.key) if top else prefix + ("`-- " if last else "|-- ") + label + " " + str(n.key)
lines.append(text)
kids = [("L", n.left), ("R", n.right)]
kids = [(s, c) for s, c in kids if c]
nxt = prefix if top else prefix + (" " if last else "| ")
for i, (s, c) in enumerate(kids):
walk(c, s, nxt, i == len(kids) - 1, False)
walk(t, "", "", True, True)
return "\n".join(lines)
def order_rules(t):
"""Return (loose, strict). loose: every left key <= node key <= every right key.
strict: every left key < node key <= every right key, the rule `insert` follows."""
loose = strict = True
def walk(n):
nonlocal loose, strict
if n is None:
return None
lo, hi = walk(n.left), walk(n.right)
if lo:
loose &= lo[1] <= n.key
strict &= lo[1] < n.key
if hi:
loose &= n.key <= hi[0]
strict &= n.key <= hi[0]
return (lo[0] if lo else n.key, hi[1] if hi else n.key)
walk(t)
return loose, strict
def tree_of(keys, tag=None):
root = None
for i, k in enumerate(keys):
root = insert(root, k, f"{tag}{i}" if tag else None)
return root
if __name__ == "__main__":
t1 = tree_of([8, 3, 10, 1, 6, 14])
t2 = tree_of([7, 3, 12, 2, 9, 15])
print("A:\n" + draw(t1) + "\n\nB:\n" + draw(t2) + "\n")
log = []
merged = [n.key for n in merge(t1, t2, log=log)]
print("\n".join(log))
print("merged:", merged, " largest stack:", merge.peak, "nodes (heights", height(t1), "and", height(t2) , "edges)")
print("\nA minus B:", difference(t1, t2))
print("B minus A:", difference(t2, t1))
w = Walker(t1)
print("\nstack of the walker on A (bottom to top), before and after each next():")
print(" start ", [n.key for n in w.stack])
while w.has():
taken = w.next().key
print(f" next -> {taken}", [n.key for n in w.stack])
for c in (12, 6, 5):
left_size = c // 2
print(f"count {c}: left half {left_size}, root 1, right half {c - left_size - 1}")
count = len(merged)
balanced = build_balanced(iter(merged), count)
print(f"\nbalanced tree from the {count} merged keys (height {height(balanced)}):\n" + draw(balanced))
loose, strict = order_rules(balanced)
print(f"left <= key <= right holds: {loose}; 'equal keys go right' holds: {strict}")
# Checks on random trees with repeated keys. Tags show who wins a tie.
rng = random.Random(3)
def tie_order_ok(nodes):
seen_b = set()
for n in nodes:
if n.tag[0] == "B":
seen_b.add(n.key)
elif n.key in seen_b:
return False # an A node came after a B node with the same key
return True
for trial in range(300):
x = [rng.randint(0, 12) for _ in range(rng.randint(0, 15))]
y = [rng.randint(0, 12) for _ in range(rng.randint(0, 15))]
a, b = tree_of(x, "A"), tree_of(y, "B")
assert order_rules(a)[1] and order_rules(b)[1] # insert really sends equal keys right
out = list(merge(a, b))
assert [n.key for n in out] == sorted(x + y)
assert tie_order_ok(out) # equal keys: tree A first
assert merge.peak <= max(height(a), height(b)) + 1
distinct_x, distinct_y = sorted(set(x)), sorted(set(y))
assert difference(tree_of(distinct_x), tree_of(distinct_y)) == sorted(set(x) - set(y))
size = len(x) + len(y)
t = build_balanced(iter(sorted(x + y)), size)
assert height(t) == (size.bit_length() - 1 if size else -1)
assert order_rules(t)[0] # left <= key <= right, equal keys allowed on both sides
print("\n300 random pairs: merge, tie order, stack bound, difference, balanced height and tree order all pass")
wrong = list(merge(tree_of([5], "A"), tree_of([5], "B"), ties_from_first=False))
print("tie check (A before B on equal keys) for a merge that prefers tree B:", tie_order_ok(wrong), "- False is the point: the check catches the flip")
chain = tree_of(range(999, -1, -1))
w = Walker(chain)
print("stack size right after creating a walker on a 1000-key chain built from descending keys:", len(w.stack))
Output:
A:
8
|-- L 3
| |-- L 1
| `-- R 6
`-- R 10
`-- R 14
B:
7
|-- L 3
| `-- L 2
`-- R 12
|-- L 9
`-- R 15
take 1 from A; stack sizes now A=2 B=3
take 2 from B; stack sizes now A=2 B=2
take 3 from A; stack sizes now A=2 B=2
take 3 from B; stack sizes now A=2 B=1
take 6 from A; stack sizes now A=1 B=1
take 7 from B; stack sizes now A=1 B=2
take 8 from A; stack sizes now A=1 B=2
take 9 from B; stack sizes now A=1 B=1
take 10 from A; stack sizes now A=1 B=1
take 12 from B; stack sizes now A=1 B=1
take 14 from A; stack sizes now A=0 B=1
merged: [1, 2, 3, 3, 6, 7, 8, 9, 10, 12, 14, 15] largest stack: 3 nodes (heights 2 and 2 edges)
A minus B: [1, 6, 8, 10, 14]
B minus A: [2, 7, 9, 12, 15]
stack of the walker on A (bottom to top), before and after each next():
start [8, 3, 1]
next -> 1 [8, 3]
next -> 3 [8, 6]
next -> 6 [8]
next -> 8 [10]
next -> 10 [14]
next -> 14 []
count 12: left half 6, root 1, right half 5
count 6: left half 3, root 1, right half 2
count 5: left half 2, root 1, right half 2
balanced tree from the 12 merged keys (height 3):
8
|-- L 3
| |-- L 2
| | |-- L 1
| | `-- R 3
| `-- R 7
| `-- L 6
`-- R 12
|-- L 10
| `-- L 9
`-- R 15
`-- L 14
left <= key <= right holds: True; 'equal keys go right' holds: False
300 random pairs: merge, tie order, stack bound, difference, balanced height and tree order all pass
tie check (A before B on equal keys) for a merge that prefers tree B: False - False is the point: the check catches the flip
stack size right after creating a walker on a 1000-key chain built from descending keys: 1000
Worked trace
Tree A's keys are 1, 3, 6, 8, 10, 14 and tree B's are 2, 3, 7, 9, 12, 15. The printed take lines are the merge: 1 (A), 2 (B), then the tie on 3, where tree A's 3 comes before tree B's 3, then 6, 7, 8, 9, 10, 12 and 14. When A runs out after 14, the drain emits B's remaining 15. The stack sizes printed after each take show the walkers never hold more than a root-to-node path: the largest is 3 nodes, which is height 2 edges plus one. The result [1, 2, 3, 3, 6, 7, 8, 9, 10, 12, 14, 15] has 12 keys, the sum of the two tree sizes.
The stack itself is the path to the next node. For tree A the walker starts with [8, 3, 1] (root 8, then its left child 3, then 1, the smallest key). next() pops 1; it has no right child, so the stack becomes [8, 3]. The next pop takes 3 and pushes the left spine of its right child: 6 has no left child, so the stack becomes [8, 6]. Pops of 6, 8 (which pushes 10, and 10 has no left child), 10 (which pushes 14) and 14 follow, ending with an empty stack.
The difference runs on the same drawn trees: A's keys not in B are [1, 6, 8, 10, 14] (3 is in both, so it is dropped from both sides) and B's keys not in A are [2, 7, 9, 12, 15]. A multiset difference would also count repeats: with A holding two 3s and B one, a set difference removes 3 completely, a multiset difference leaves one 3.
build_balanced on the 12 merged keys gives the drawn tree of height 3 (the two 3s end up one inside the other's left subtree, so only the left <= key <= right rule holds, as the line after the drawing says): root 8 has 6 keys on its left (1, 2, 3, 3, 6, 7) and 5 on its right (9, 10, 12, 14, 15), exactly the split printed on the count 12 line.
Complexity
- Time: O(m + n). Every node is pushed once and popped once across both walkers, and every loop step pops one node.
- Space: O(h1 + h2) beyond the output: each stack holds at most h + 1 nodes of its tree.
mergeuses no recursion, so a deeply skewed tree cannot hit Python's recursion limit of about 1000 frames (a recursive in-order generator would). The output list is not counted. - A degenerate tree ruins the space bound: a tree built from keys in descending order is a chain of left children with h = size - 1, so the walker's stack holds the whole tree (the last output line: 1000 nodes on the stack right after creating the walker), and O(h1 + h2) becomes O(m + n). The bound is only a saving when the trees are reasonably balanced.
- Balanced rebuild: O(m + n) time, and the new tree is the output; the recursion adds O(log(m + n)).
Edge cases and common mistakes
- Either tree empty: its walker has no nodes, and the other tree is drained.
- Equal keys across trees and repeated keys inside a tree both come out in sorted order, and the trees built with
insertobey the "equal keys go right" rule (the random run asserts it). The tag check in the program (each node carries a tag such as A3) confirms that for equal keys the A node comes before the B node, and a merge that prefers B on ties fails that same check: thetie checkline printsFalseon purpose, to show the check catches the flip. - Comparing with
<=when taking from B instead of<silently flips the tie order. - Forgetting to push the left spine of the right child after a pop, which skips nodes.
- Using a plain recursive in-order traversal for each tree: two recursions cannot be interleaved, so you would need generators, and a skewed tree deeper than Python's recursion limit would fail.
- For the difference, assuming sets. If keys repeat inside A, say whether the result is a set difference or a multiset difference;
differenceas written gives the multiset result, where each copy of a key in B cancels one copy of it in A.
Running the code
docker run --rm -v "$PWD":/w -w /w python:3.12 python bst_merge.py
Save the code block above as bst_merge.py; it uses only the standard library.
Compute the height of a binary tree, recursively and then iteratively with BFS. Say up front what you return for an empty tree and for a single node, and what the stack depth is on a skewed tree.
Sample Answer
The idea in plain words
The height of a tree is the length of the longest path from the root down to a leaf. Counting here is in edges (the lines between parent and child): an empty tree has height -1, a single node has height 0, and in general height(node) = 1 + max(height(left), height(right)). Recursion follows that formula directly. The iterative version walks the tree level by level with a queue (breadth-first search, BFS) and counts how many levels it passed through.
Approach
Recursive. The height of a node is one more than the taller of its two subtrees. The empty tree is the base case and returns -1, which makes a leaf come out as 1 + max(-1, -1) = 0.
Iterative with BFS. Keep a queue of the current level. Each pass removes all nodes of that level and adds all of their children, which is the next level. Count the passes; the height is the pass count minus one (edges, not levels), which the code does by starting the counter at -1.
Code
from collections import deque
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height_recursive(node):
if node is None:
return -1 # empty tree
return 1 + max(height_recursive(node.left), height_recursive(node.right))
def height_bfs(root):
if root is None:
return -1
height = -1
queue = deque([root])
while queue:
height += 1 # one more level has been reached
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return height
def depth_of(root, target):
"""Edges from the root to the first node holding target, or -1 if absent."""
queue = deque([(root, 0)] if root else [])
while queue:
node, depth = queue.popleft()
if node.val == target:
return depth
for child in (node.left, node.right):
if child:
queue.append((child, depth + 1))
return -1
# 7
# / \
# 3 9
# \ \
# 5 12
# /
# 11
tree = TreeNode(7, TreeNode(3, None, TreeNode(5)), TreeNode(9, None, TreeNode(12, TreeNode(11))))
leaf = TreeNode(1)
print("recursive:", height_recursive(tree), height_recursive(leaf), height_recursive(None))
print("bfs :", height_bfs(tree), height_bfs(leaf), height_bfs(None))
print("depth of 11:", depth_of(tree, 11), "| depth of 7:", depth_of(tree, 7), "| depth of 99:", depth_of(tree, 99))
for n in (900, 5000):
chain = None
for i in range(n):
chain = TreeNode(i, right=chain)
try:
print(f"chain of {n}: recursive", height_recursive(chain), "| bfs", height_bfs(chain))
except RecursionError:
print(f"chain of {n}: recursive RecursionError | bfs", height_bfs(chain))
Output:
recursive: 3 0 -1
bfs : 3 0 -1
depth of 11: 3 | depth of 7: 0 | depth of 99: -1
chain of 900: recursive 899 | bfs 899
chain of 5000: recursive RecursionError | bfs 4999
Worked example
7
/ \
3 9
\ \
5 12
/
11
The longest path is 7, 9, 12, 11, which is 3 edges, so the height is 3. Both functions print 3 for this tree, 0 for a single node (leaf), and -1 for the empty tree.
The BFS passes on this tree: [7] (counter goes from -1 to 0), [3, 9] (1), [5, 12] (2), [11] (3). The queue is then empty and the counter holds 3.
Conventions
- Edges versus nodes. Counting nodes on the longest path gives the edge answer plus 1: empty tree 0, single node 1. Problems that ask for "maximum depth" usually mean this node-count version. Say which one you use before you code, and make the base case match.
- Depth of a given node: the number of edges from the root to a node holding a given value.
depth_offinds it with BFS, carrying the depth next to each queued node, and returns -1 when the value is absent: it gives 3 for 11, 0 for the root 7, and -1 for 99. - In C++ the same recursive function returns
int, takesTreeNode*, and checksroot == nullptrfirst; the structure is identical.
Stack depth on a skewed tree
A skewed tree is one where every node has a single child, so the tree is a chain. The recursive function has one pending call per node on the path, plus the call on the empty child, so a chain of n nodes uses about n + 1 stack frames at the deepest point: the stack depth equals the height plus a small constant. CPython allows 1000 frames by default. The demo shows the result: a chain of 900 nodes works (height 899) but a chain of 5,000 raises RecursionError, while the BFS version returns 4999 on the same input. In languages such as Java or C++ the limit is the thread's stack size rather than a fixed frame count, and a very deep chain fails there as well.
Complexity
| Version | Time | Extra space |
|---|---|---|
| Recursive | O(n) | O(h) call stack, so up to n on a chain |
| BFS | O(n) | O(w) queue, where w is the widest level: up to about n / 2 on a full tree, 1 on a chain |
Here n is the number of nodes and h the height. Each node is handled once in both. The two versions trade stack depth against queue width, so BFS is the one to use when the tree might be a deep chain, and the recursive form is fine for balanced trees.
Edge cases and common mistakes
- Empty tree: -1 here. In a node-counting version it is 0. Decide before writing the base case.
- Single node: 0 edges.
- Using
list.pop(0)for the queue, which is O(n) per pop;collections.deque.popleft()is O(1). - Incrementing the counter once per node instead of once per level. With the counter starting at -1 as here, that returns the node count minus 1 (5 for the 6-node example tree instead of 3); starting the counter at 0 would return the node count itself. Either way it is not the height.
- Taking
maxof the heights but forgetting the1 +, so every tree reports -1.
Running the code
Save the code block as tree_height.py and run python3 tree_height.py with Python 3.12. Only the standard library is used.
When would you choose a BST over a hash map or a sorted array? Compare lookup speed, insertion cost, ordered traversal and range queries, and memory.
Sample Answer
Direct answer
Choose a binary search tree (BST) when you need both changing data and order: you keep inserting and deleting keys, and you also need sorted iteration, minimum and maximum, the next larger key, or "everything between A and B". A hash map is better when you only ever ask "is this exact key here?". A sorted array is better when the data rarely changes, because it is compact and binary search on it is very fast.
A BST keeps smaller keys in the left subtree and larger keys in the right subtree of every node. Inserting 50, 30, 70, 20, 40 gives this tree (height 2; heights count edges, so the empty tree is -1 and a single node is 0):
50
/ \
30 70
/ \
20 40
Reading it left subtree, node, right subtree (in-order) gives 20, 30, 40, 50, 70: sorted, with no sorting step.
Comparison
| Hash map | Sorted array | Balanced BST | |
|---|---|---|---|
| Lookup | O(1) expected | O(log n) binary search | O(log n) |
| Insert | O(1) expected | O(n): elements after the position shift | O(log n) |
| Delete | O(1) expected | O(n) | O(log n) |
| Ordered traversal | needs a sort, O(n log n) | O(n), already ordered | O(n) |
| Range query (k results) | scan all n entries, O(n) | O(log n + k) | O(log n + k) |
| Min, max, next larger | O(n) | O(1) / O(log n) | O(log n) |
| Memory | table plus spare capacity | smallest: just the values, contiguous | two child pointers per key, one allocation per node |
"Balanced" matters: a plain BST built from sorted input degenerates into a chain, every node having a single child:
chain (keys 1 to 5 inserted in order) balanced (same keys)
1 3
\ / \
2 2 4
\ / \
3 1 5
\
4
\
5
Finding 5 compares against 1, 2, 3, 4, 5 in the chain but only 3, 4, 5 in the balanced tree, and the gap grows with n. In the chain every operation becomes O(n), so in production use a self-balancing tree (AVL or red-black, two designs that rotate nodes after updates to keep the height small) or a library ordered map. Python's dict keeps insertion order, not key order, so it does not give you sorted iteration.
Measured on 1,000 random keys
The program builds all three structures from the same keys (seed 5) and counts comparisons, shifted elements and visited nodes.
import random
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def bst_insert(root, key):
"""Returns (root, comparisons)."""
if root is None:
return Node(key), 0
cur, steps = root, 0
while True:
steps += 1
side = "left" if key < cur.key else "right"
nxt = getattr(cur, side)
if nxt is None:
setattr(cur, side, Node(key))
return root, steps
cur = nxt
def bst_find(root, key):
cur, steps = root, 0
while cur:
steps += 1
if key == cur.key:
return True, steps
cur = cur.left if key < cur.key else cur.right
return False, steps
def bst_range(node, lo, hi, out, visited):
"""Keys in [lo, hi] in sorted order; skips subtrees that cannot contain any."""
if node is None:
return
visited[0] += 1
if lo < node.key:
bst_range(node.left, lo, hi, out, visited)
if lo <= node.key <= hi:
out.append(node.key)
if node.key < hi:
bst_range(node.right, lo, hi, out, visited)
def bst_height(root):
h, level = -1, [root] if root else []
while level:
h += 1
level = [c for n in level for c in (n.left, n.right) if c]
return h
def lower_bound(a, x):
"""First index with a[i] >= x, and the comparisons used (binary search)."""
lo, hi, steps = 0, len(a), 0
while lo < hi:
steps += 1
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo, steps
if __name__ == "__main__":
random.seed(5)
keys = random.sample(range(100_000), 1000) # distinct keys, random arrival order
root = None
for k in keys:
root, _ = bst_insert(root, k)
table = {k: True for k in keys} # hash map
arr = sorted(keys) # sorted array
# Lookup: average comparisons over every stored key
bst_avg = sum(bst_find(root, k)[1] for k in keys) / len(keys)
arr_avg = sum(lower_bound(arr, k)[1] for k in keys) / len(keys)
print(f"lookup, average comparisons: BST {bst_avg:.1f} (height {bst_height(root)}), sorted array {arr_avg:.1f}, hash map: 1 hash + about 1 probe")
# Insert one new key that lands in the middle of the order
new = 50_001
_, bst_steps = bst_insert(root, new)
idx, find_steps = lower_bound(arr, new)
print(f"insert {new}: BST {bst_steps} comparisons, sorted array {find_steps} comparisons + {len(arr) - idx} elements shifted")
# Range query: keys between 40000 and 41999
lo, hi = 40_000, 41_999
out, visited = [], [0]
bst_range(root, lo, hi, out, visited)
start, c1 = lower_bound(arr, lo)
end, c2 = lower_bound(arr, hi + 1)
in_hash = sorted(k for k in table if lo <= k <= hi)
assert out == arr[start:end] == in_hash
print(f"range [{lo}, {hi}] returns {len(out)} keys:")
print(f" BST visits {visited[0]} nodes, sorted array uses {c1 + c2} comparisons + {end - start} copies, hash map examines all {len(table)} entries, then sorts the {len(in_hash)} hits")
print("smallest 3 keys in order:", arr[:3], "| BST in-order gives the same without a sort step")
Output:
lookup, average comparisons: BST 11.8 (height 20), sorted array 10.0, hash map: 1 hash + about 1 probe
insert 50001: BST 13 comparisons, sorted array 10 comparisons + 473 elements shifted
range [40000, 41999] returns 25 keys:
BST visits 40 nodes, sorted array uses 19 comparisons + 25 copies, hash map examines all 1000 entries, then sorts the 25 hits
smallest 3 keys in order: [9, 57, 86] | BST in-order gives the same without a sort step
Reading the output
- Lookup: the BST used about 11.8 comparisons on average (its height is 20 because it is not balanced); the sorted array used about 10.0. A hash map does one hash computation and about one probe. The hash function turns the key into a slot number, a probe is one look at one slot, and a collision is two keys that want the same slot, which the table resolves by looking at another slot. With a table that is not too full, most lookups need one or two probes whatever the number of keys, which is why the cost is called expected O(1); the small program below shows what a probe and a collision look like on 8 slots.
- Binary search (
lower_bound): it keeps a window[lo, hi)of positions that could still hold the answer, looks at the middle, and discards the half that cannot contain it. The window halves every step, so 1,000 elements need about 10 steps, as the output shows. - Insert: the array found the position in 10 comparisons but then had to shift 473 elements to make room, the cost that grows with n. The BST changed one pointer after 13 comparisons.
- Range query returning 25 keys: the BST visited 40 nodes, the array used 19 comparisons plus 25 copies, and the hash map had to look at all 1,000 entries and then sort the 25 hits.
- Why 40 nodes for 25 results:
bst_rangeenters a node, goes left only iflo < node.key, records the key if it is inside[lo, hi], and goes right only ifnode.key < hi. The 25 in-range nodes are visited once each. The other visited nodes are the ones passed on the way down to the first and last key of the range, the two lookup paths. That is the O(log n + k) shape: find the start in O(log n), then read the k results in order.
Where the 40 visits and the probes come from
The program below reuses the same 1,000 keys (seed 5) and range, splits the 40 visited nodes into the 25 inside the range and the rest, checks that the rest lie on the two lookup paths, and runs a hash table with 8 slots and linear probing (on a collision, try the next slot) on five integer keys. Real hash maps use more elaborate probing, but a probe still means one look at one slot.
import random
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def bst_insert(root, key):
if root is None:
return Node(key)
cur = root
while True:
side = "left" if key < cur.key else "right"
nxt = getattr(cur, side)
if nxt is None:
setattr(cur, side, Node(key))
return root
cur = nxt
def bst_range_visits(node, lo, hi, visited):
"""Keys of every node the range walk enters, in visiting order."""
if node is None:
return
visited.append(node.key)
if lo < node.key:
bst_range_visits(node.left, lo, hi, visited)
if node.key < hi:
bst_range_visits(node.right, lo, hi, visited)
def lookup_path(root, key):
path, cur = [], root
while cur:
path.append(cur.key)
if key == cur.key:
break
cur = cur.left if key < cur.key else cur.right
return path
random.seed(5)
keys = random.sample(range(100_000), 1000)
root = None
for k in keys:
root = bst_insert(root, k)
lo, hi = 40_000, 41_999
visited = []
bst_range_visits(root, lo, hi, visited)
inside = [k for k in visited if lo <= k <= hi]
outside = [k for k in visited if not lo <= k <= hi]
path_lo, path_hi = lookup_path(root, lo), lookup_path(root, hi)
print(f"range walk visited {len(visited)} nodes: {len(inside)} inside the range, {len(outside)} outside")
print(f"lookup path for {lo} has {len(path_lo)} nodes, lookup path for {hi} has {len(path_hi)} nodes")
print("every outside node lies on one of the two lookup paths:", all(k in path_lo or k in path_hi for k in outside))
# A hash table with 8 slots and linear probing: a probe is one look at one slot.
slots = [None] * 8
def put(key):
i = key % 8 # the hash function: key modulo the table size
probes = 1
while slots[i] is not None: # collision: the slot is taken, try the next one
i = (i + 1) % 8
probes += 1
slots[i] = key
return probes
def get(key):
i, probes = key % 8, 1
while slots[i] != key:
i = (i + 1) % 8
probes += 1
return probes
for key in (10, 18, 3, 26, 7):
print(f"put {key}: hash slot {key % 8}, probes {put(key)}")
print("table:", slots)
print("probes to find each key:", {key: get(key) for key in (10, 18, 3, 26, 7)})
# A chain versus a balanced tree on the same five keys.
chain = None
for k in (1, 2, 3, 4, 5):
chain = bst_insert(chain, k)
balanced = None
for k in (3, 2, 4, 1, 5):
balanced = bst_insert(balanced, k)
print("lookup path for 5 in the chain:", lookup_path(chain, 5), "| in the balanced tree:", lookup_path(balanced, 5))
Output:
range walk visited 40 nodes: 25 inside the range, 15 outside
lookup path for 40000 has 13 nodes, lookup path for 41999 has 16 nodes
every outside node lies on one of the two lookup paths: True
put 10: hash slot 2, probes 1
put 18: hash slot 2, probes 2
put 3: hash slot 3, probes 2
put 26: hash slot 2, probes 4
put 7: hash slot 7, probes 1
table: [None, None, 10, 18, 3, 26, None, 7]
probes to find each key: {10: 1, 18: 2, 3: 2, 26: 4, 7: 1}
lookup path for 5 in the chain: [1, 2, 3, 4, 5] | in the balanced tree: [3, 4, 5]
The range walk visits 15 nodes outside the range, and each one lies on the lookup path of the lowest or the highest key, so the extra visits are bounded by the length of those two paths (at most about twice the height), not by n. In the hash table, key 10 lands in its own slot with 1 probe; 18 hashes to the same slot 2, finds it taken and needs 2 probes; 26 also hashes to slot 2 and needs 4. Lookups repeat the same probe sequence, so a crowded table costs more probes, which is why a hash map keeps spare capacity. The last line is the chain drawing above as code: 5 steps in the chain, 3 in the balanced tree.
Decision rule
- Static or bulk-loaded data with lookups and ranges: sorted array.
- Exact-key lookups, no order needed, heavy writes: hash map.
- Heavy writes and order or range queries (leaderboards, time windows, scheduling, "nearest key"): balanced BST.
Pitfalls
- Quoting O(log n) for a BST without saying it is balanced.
- Forgetting that the hash map's O(1) is expected, not guaranteed, and that it needs a good hash function.
- Counting only comparisons and ignoring that an array insert moves O(n) elements.
- Writing the range query recursively on a degenerate tree: depth equals the height, and CPython's default limit is 1,000 frames.
Running the code
Save the listing as bst_vs_hash.py and run python3 bst_vs_hash.py (Python 3.12, standard library only). The program in the section above is self-contained: save it as range_and_probes.py and run it the same way.
How do binary-tree traversals relate to depth-first search on a graph? Show how DFS over a tree stored as adjacency lists yields preorder and postorder, and explain why inorder only makes sense for binary trees.
Sample Answer
The idea
A tree is a graph that is connected and has no cycles, so a binary-tree traversal is depth-first search (DFS: go as deep as possible along one path, then back up and try the next) run on that graph. The three classic orders differ only in WHEN you write a node down:
- Preorder: the moment DFS first enters the node (before any child).
- Postorder: the moment DFS leaves the node (after every child is finished).
- Inorder: between the left child's subtree and the right child's subtree. This is the one that has no graph equivalent, as explained below.
(Depth and height here count edges, so a single node has height 0 and the empty tree has height -1.)
DFS over adjacency lists gives preorder and postorder
An adjacency list stores, for each node, the nodes it is linked to. For an undirected tree, each child also lists its parent, so DFS needs a visited set (or a "came from" parent argument) to avoid walking back up. Record the node on entry for preorder and on exit for postorder. For this tree:
1
/ \
2 3
/ \
4 5
def dfs_orders(adj, start, trace=False):
"""Graph DFS with a visited set. Record a node when it is entered (preorder)
and when all its neighbours are finished (postorder)."""
pre, post, visited = [], [], set()
def visit(node, depth=0):
visited.add(node)
pre.append(node)
if trace:
print(" " * depth + f"enter {node} (preorder so far {pre})")
for neighbour in adj[node]:
if neighbour not in visited:
visit(neighbour, depth + 1)
post.append(node)
if trace:
print(" " * depth + f"leave {node} (postorder so far {post})")
visit(start)
return pre, post
# The same tree as a binary tree and as an undirected adjacency list.
# 1
# / \
# 2 3
# / \
# 4 5
adj = {1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}
print(dfs_orders(adj, 1, trace=True))
# Binary-tree versions: children are (left, right) pairs.
children = {1: (2, 3), 2: (4, 5), 3: (None, None), 4: (None, None), 5: (None, None)}
def tree_orders(node, pre, ino, post):
if node is None:
return
pre.append(node)
tree_orders(children[node][0], pre, ino, post)
ino.append(node)
tree_orders(children[node][1], pre, ino, post)
post.append(node)
pre, ino, post = [], [], []
tree_orders(1, pre, ino, post)
print(pre, ino, post)
# Inorder needs "left" and "right" as separate slots. A bare adjacency list loses that:
tree_a = {1: (2, None), 2: (None, None)} # 2 is the LEFT child of 1
tree_b = {1: (None, 2), 2: (None, None)} # 2 is the RIGHT child of 1
def inorder(tree, node):
if node is None:
return []
left, right = tree[node]
return inorder(tree, left) + [node] + inorder(tree, right)
same_adj = {1: [2], 2: [1]}
print(dfs_orders(same_adj, 1), "<- one adjacency list")
print(inorder(tree_a, 1), inorder(tree_b, 1), "<- two different binary trees")
# Iterative DFS with an explicit stack, safe on a 5000-node chain.
chain = {i: [j for j in (i - 1, i + 1) if 0 <= j < 5000] for i in range(5000)}
def dfs_orders_iterative(adj, start, trace=False):
pre, post, visited = [], [], {start}
pre.append(start)
stack = [(start, iter(adj[start]))]
while stack:
node, it = stack[-1]
for nxt in it:
if nxt not in visited:
visited.add(nxt)
pre.append(nxt)
stack.append((nxt, iter(adj[nxt])))
if trace:
print(f"push {nxt}: stack {[n for n, _ in stack]}")
break
else:
post.append(node)
stack.pop()
if trace:
print(f"pop {node}: stack {[n for n, _ in stack]}")
return pre, post
dfs_orders_iterative(adj, 1, trace=True)
print(dfs_orders_iterative(adj, 1) == dfs_orders(adj, 1))
p, q = dfs_orders_iterative(chain, 0)
print(len(p), p[:3], q[:3])
try:
dfs_orders(chain, 0)
except RecursionError:
print("recursive version: RecursionError on the 5000-node chain")
Output
enter 1 (preorder so far [1])
enter 2 (preorder so far [1, 2])
enter 4 (preorder so far [1, 2, 4])
leave 4 (postorder so far [4])
enter 5 (preorder so far [1, 2, 4, 5])
leave 5 (postorder so far [4, 5])
leave 2 (postorder so far [4, 5, 2])
enter 3 (preorder so far [1, 2, 4, 5, 3])
leave 3 (postorder so far [4, 5, 2, 3])
leave 1 (postorder so far [4, 5, 2, 3, 1])
([1, 2, 4, 5, 3], [4, 5, 2, 3, 1])
[1, 2, 4, 5, 3] [4, 2, 5, 1, 3] [4, 5, 2, 3, 1]
([1, 2], [2, 1]) <- one adjacency list
[2, 1] [1, 2] <- two different binary trees
push 2: stack [1, 2]
push 4: stack [1, 2, 4]
pop 4: stack [1, 2]
push 5: stack [1, 2, 5]
pop 5: stack [1, 2]
pop 2: stack [1]
push 3: stack [1, 3]
pop 3: stack [1]
pop 1: stack []
True
5000 [0, 1, 2] [4999, 4998, 4997]
recursive version: RecursionError on the 5000-node chain
Worked trace
The indented lines at the top of the output are the DFS events for the tree above, printed by the same function with trace=True. The recursion enters 1, then 2, then 4; 4 has no unvisited neighbour, so it is left (postorder starts [4]); then 5 is entered and left; then 2 is left, then 3 is entered and left, and finally 1 is left. Preorder is [1, 2, 4, 5, 3] (order of entry) and postorder is [4, 5, 2, 3, 1] (order of exit). The next output line shows that the binary-tree functions produce the same preorder and postorder, plus inorder [4, 2, 5, 1, 3]. The match holds because the adjacency list names each node's children in left-then-right order.
The iterative version, step by step
Recursion keeps, for every node still being explored, a paused place in that node's neighbour list. The explicit stack does the same job by hand: each entry is a pair (node, iterator), where iter(adj[node]) is a bookmark into that node's neighbours that remembers how far you have read. Storing the bookmark is what lets you come back to a node and carry on with its next neighbour instead of restarting its list.
The loop looks at the top pair and pulls neighbours from its iterator:
- If it finds an unvisited neighbour, it records that neighbour in preorder (first entry), pushes a new pair for it, and
breaks out of theforso the loop restarts with the new top. - A Python
for ... elseruns itselseblock only when theforfinished without hittingbreak. Here that means the iterator is used up: every neighbour was already visited or fully explored. So theelsebranch is exactly "this node is finished": append it to postorder and pop it.
That is why postorder is appended only in the else branch: a node is left only after all its neighbours are exhausted, whereas preorder is appended at push time, the first moment the node is reached.
Run on the 5-node tree, the trace lines show the stack holding the path from the start down to the node being explored (node ids only, bookmarks omitted). The pushes happen in the order 2, 4, 5, 3, which is the preorder [1, 2, 4, 5, 3], and the pops happen in the order 4, 5, 2, 3, 1, which is the postorder [4, 5, 2, 3, 1]. Node 1 is never popped until the end because it sits at the bottom of the stack while its descendants are explored. The stack never holds more than one root-to-node path, which is why its size is the height plus one, not the node count.
Why inorder only makes sense for binary trees
Inorder means "left subtree, then this node, then right subtree". That needs exactly two distinguishable child slots with the node placed between them.
- In an adjacency list a node with one child just shows one neighbour, with no record of whether it is the left or the right child. The code above builds two different binary trees (2 as the left child of 1, then 2 as the right child of 1) that share one adjacency list
{1: [2], 2: [1]}. DFS gives([1, 2], [2, 1])for the list, while inorder gives[2, 1]for one tree and[1, 2]for the other. - A node with three or more children has several gaps between its subtrees, so "in the middle" is not defined; any rule you pick (after the first child, after the second) is a convention, not a natural order.
- On a general graph with cycles there is no "left" or "right" at all. DFS still gives a preorder and a postorder (they depend on the start node and the neighbour order), but only the visited set keeps it from looping forever.
Complexity
DFS over adjacency lists is O(V + E) time, where V is nodes and E is edges; a tree has E = V - 1 edges, so this is O(n). Space for the recursion is O(h) frames (h is the height in edges), and the visited set in this code adds O(n); passing the parent instead of using a visited set on a tree brings the total back to O(h).
Edge cases and common mistakes
- Skewed tree and the recursion limit: CPython's default limit is 1000 nested calls, so the recursive
dfs_ordersraisesRecursionErroron a 5000-node chain, as the last output line shows. The iterative version (explicit stack of(node, iterator)pairs) handles it and gives the same orders on the small tree. - Forgetting the visited check on undirected adjacency lists makes DFS bounce between a parent and its child forever (until the recursion limit).
- Recording a node on exit and calling it preorder (or the reverse) is the commonest slip; the only difference is which line of the code appends.
- Treating inorder as "DFS with some other timing" without left/right information produces answers that depend on adjacency order.
Running the code
Save as dfs_orders.py and run python3 dfs_orders.py (Python 3.12, standard library only).
Unlock Full Question Bank
Get access to all Trees and Binary Search Trees interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.