Binary Trees & Traversals
A binary tree is either empty, or a node holding a value together with two binary trees, its left and right subtrees. That recursive definition is the whole subject in one sentence. Every algorithm on this page is the definition read aloud: handle the empty tree, handle the node, recurse into the two subtrees. What changes from one algorithm to the next is when you handle the node relative to the recursion and what you use to remember where you have been — the call stack, an explicit stack, a queue, or, in Morris traversal, the tree's own unused pointers.
This page is the vocabulary and toolkit for the rest of Module 3: shape terms and counting facts, every traversal recursive and iterative, Morris traversal in space, serialization with a uniqueness proof, construction from two traversals, and the Catalan numbers.
Why this exists
Linear structures answer "what comes next?". Trees answer "what is inside what?". File systems, HTML documents, parsed programs, arithmetic expressions and database indexes are all trees. Whenever each piece of data belongs to exactly one parent piece, a tree is its natural shape, and a traversal visits every piece in an order that respects the hierarchy.
Binary trees are the simplest trees with enough structure to support ordered search (BSTs), priority (heaps), range aggregation (segment trees) and expression evaluation. Any ordered tree of arbitrary fan-out can be encoded as a binary tree (the left-child right-sibling encoding below), so binary-tree algorithms are general-purpose.
The orders are old. Prefix ("Polish") notation, due to Łukasiewicz in the 1920s, is preorder of an expression tree; its reverse, postfix, is postorder. Perlis and Thornton introduced threaded binary trees in 1960, reusing null pointers to reach the inorder successor without a stack; Joseph Morris made the threads temporary in 1979. In production, the traversal you pick decides whether code overflows the stack on a degenerate input and how much memory a scan of a huge tree costs.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
"root", "left child", "right child", TreeNode, a level-order array with nulls | Binary tree; parse with the level-order builder below |
| "in sorted order", "k-th smallest", a BST plus "iterate" | Inorder traversal (iterative, so you can stop early) |
| "copy", "clone", "serialize", "print the structure", "prefix expression" | Preorder (node before children) |
| "delete", "free", "evaluate", "size of each subtree", "postfix", anything that needs the children's answers first | Postorder (children before node) |
| "level by level", "each depth", "minimum depth", "nearest", "width", "connect next pointers" | Level-order (BFS) with a level-size snapshot |
| "zigzag", "spiral", "alternate direction" | Level order, reverse every other level |
| "vertical", "column", "top view", "bottom view" | BFS or DFS carrying a column index |
| "O(1) extra space", "without recursion or a stack", "recover a BST with two swapped nodes in constant space" | Morris traversal |
| "encode / decode", "send over the network", "store and restore" | Preorder with null markers, or level order with null markers |
| "construct from preorder and inorder" (or postorder and inorder) | Root from one traversal, split from the inorder position (hash map for ) |
| "construct from preorder and postorder" | Ambiguous unless the tree is full; return any valid tree |
| "how many structurally different trees / BSTs", "number of ways to parenthesize" | Catalan numbers |
| recursion depth could reach (skewed trees, linked-list-shaped input) | Iterative traversal with an explicit stack, or Morris |
Intuition & first principles
Vocabulary
Fix one binary tree. The node with no parent is the root. A node with no children is a leaf; a node with at least one child is internal. The depth of a node is the number of edges from the root to it, so the root has depth 0. The height of a node is the number of edges on the longest downward path from it to a leaf, so a leaf has height 0; the height of the tree is the height of its root, and by convention the empty tree has height . A level is the set of nodes at one depth. The subtree rooted at is together with all its descendants. If lies on the path from the root to , then is an ancestor of and is a descendant of (every node is its own ancestor in most proofs; say "proper ancestor" to exclude it).
Height conventions differ
Some books and LeetCode's "maximum depth" count nodes instead of edges, so a single node has height 1. This page counts edges.
Shapes: full, complete, perfect, balanced
These words are used loosely; the course uses these meanings (sources differ, notably on "complete", so check definitions).
- Full (proper, strict): every node has 0 or 2 children. Expression trees with binary operators are full.
- Perfect: full, with all leaves at the same depth, so every level is filled.
- Complete: every level filled except possibly the last, whose nodes are packed to the left. Binary heaps are complete, which is what lets them live in an array.
- Height-balanced: at every node the subtree heights differ by at most 1 (the AVL condition). Loosely, "balanced" means height .
flowchart LR
subgraph Perfect["perfect h=2"]
P1((1)) --> P2((2))
P1 --> P3((3))
P2 --> P4((4))
P2 --> P5((5))
P3 --> P6((6))
P3 --> P7((7))
end
subgraph Complete["complete, not full"]
C1((1)) --> C2((2))
C1 --> C3((3))
C2 --> C4((4))
end
subgraph Full["full, not complete"]
F1((1)) --> F2((2))
F1 --> F3((3))
F3 --> F6((6))
F3 --> F7((7))
end
Every perfect tree is complete and full; a complete tree need not be full (node 2 above has one child); a full tree need not be complete (the right side is deeper than the left). Every complete tree is height-balanced, but a height-balanced tree need not be complete.
Counting facts and their proofs
Level capacity. Level holds at most nodes. Proof by induction on : level 0 holds the root alone, and each node on level contributes at most two nodes to level .
Perfect trees. A perfect tree of height has
nodes, of which — just over half — are leaves. That fact is why the bottom level dominates the cost of heap construction.
Height bounds. For any binary tree with nodes,
The upper bound is a path (every node has one child). For the lower bound, a tree of height has at most nodes, so , i.e. , so and therefore . A complete tree achieves the lower bound: a million-element heap has height . The gap between 19 and 999,999 is why Module 3 spends two lessons on balancing.
Null pointers. A binary tree with nodes stored with left and right pointers has exactly null child pointers.
Proof. Each node has two child slots, slots in total. Every node except the root sits in exactly one slot — its parent's — and no slot holds two nodes, so exactly slots are filled. The remaining slots are null.
So more than half of a linked tree's pointer fields are null (the observation behind threaded trees and Morris traversal), and a preorder serialization with null markers has exactly one more marker than values. A cousin:
Full trees. A full binary tree with internal nodes has leaves. Proof. Count edges two ways: every internal node has exactly two child edges, so there are edges; a tree with nodes has edges. So , giving . An expression with binary operators therefore has operands.
Representations
Linked nodes. The default: an object with val, left, right. Any shape, but every node is a separate allocation, so traversal is a pointer chase that can miss cache on each step (How Data Structures Live in Memory).
Parent pointers. A parent field lets you walk up: the inorder successor becomes an walk with no stack and an iterator is a single pointer. The red-black trees inside std::map and the Linux kernel's rbtree store parents because rebalancing walks up from the insertion point.
Implicit array (heap layout). Store a complete tree level by level: node has children , and parent (0-indexed). No pointers, perfect locality — but only for complete trees, since a tree of height needs slots. Heaps and segment trees live on this layout.
Level order with null markers (the LeetCode format). [1, 2, 3, 4, 5, null, 6, null, null, 7, 8] is not the heap layout. It lists nodes in BFS order; each null is a missing child of a node that exists, and children of missing nodes are not written. The builder reads it with a queue: pop a parent, attach the next two entries, push the non-null ones. Every code block on this page and the next uses it.
Left-child right-sibling. Any ordered tree becomes binary by storing each node's first child as left and its next sibling as right; preorder is preserved. The DOM's firstChild / nextSibling is this representation made visible.
The three depth-first orders
Walk around the outside of the tree, starting at the root and keeping the tree on your left, like tracing a coastline. You pass every node three times: once on the way down its left side, once underneath it between its two subtrees, and once on the way up its right side. Emit the node on the first pass and you get preorder; on the second, inorder; on the third, postorder. Precisely:
- Preorder: node, then preorder(left), then preorder(right).
- Inorder: inorder(left), then node, then inorder(right).
- Postorder: postorder(left), then postorder(right), then node.
Level order is different in kind: it visits nodes by depth, left to right within a depth, which is breadth-first search on the tree.
Here is the example tree the rest of this page uses, built from the level-order array [1, 2, 3, 4, 5, null, 6, null, null, 7, 8]:
flowchart TD
n1((1)) --> n2((2))
n1 --> n3((3))
n2 --> n4((4))
n2 --> n5((5))
n3 -.-> x1["null"]
n3 --> n6((6))
n5 --> n7((7))
n5 --> n8((8))
| Order | Sequence | Why it looks like that |
|---|---|---|
| Preorder | 1, 2, 4, 5, 7, 8, 3, 6 | Each node precedes its entire subtree |
| Inorder | 4, 2, 7, 5, 8, 1, 3, 6 | Each node sits between its left and right subtrees |
| Postorder | 4, 7, 8, 5, 2, 6, 3, 1 | Each node follows its entire subtree; root is last |
| Level order | 1 | 2, 3 | 4, 5, 6 | 7, 8 | Depth 0, 1, 2, 3 |
| Zigzag | 1 | 3, 2 | 4, 5, 6 | 8, 7 | Odd depths reversed |
All rows were produced by the implementations below. Memorise two facts the construction algorithms use: preorder starts with the root and postorder ends with it, with every subtree a contiguous block; in inorder the root splits the left subtree's block from the right's.
Mechanics
Recursive traversals
The recursive versions are the definitions transcribed:
# fragment — the three recursive orders (full runnable versions in the Implementation section)
def preorder(node, out):
if node is None:
return
out.append(node.val) # pre: before both subtrees
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.val) # in: between the subtrees
inorder(node.right, out)
def postorder(node, out):
if node is None:
return
postorder(node.left, out)
postorder(node.right, out)
out.append(node.val) # post: after both subtrees
There is one call per node plus one per null pointer — calls by the null-pointer theorem — and the call stack holds the current root-to-node path, so extra space is . On a path that is : CPython's default recursion limit is 1,000 frames, and a JVM thread's default stack usually overflows in the low tens of thousands of frames (it depends on frame size and -Xss). The iterative versions move the stack to the heap.
Iterative preorder: one stack
Preorder is the easiest to make iterative because the node is emitted the moment you first reach it. Push the root; repeatedly pop a node, emit it, and push its right child then its left child, so the left child is popped first.
# fragment — iterative preorder
def preorder_iter(root):
out, stack = [], [root] if root else []
while stack:
node = stack.pop()
out.append(node.val)
if node.right: stack.append(node.right) # pushed first, popped later
if node.left: stack.append(node.left)
return out
The stack is a to-do list of subtree roots whose preorder has not started. Popping the left child before the right reproduces "left subtree, then right subtree". The stack can hold up to about pending right children — .
Iterative inorder: the go-left loop
Inorder emits a node only after its whole left subtree. So when you reach a node you cannot emit it yet; you push it as a reminder and go left. When you fall off the tree (cur is null), the node on top of the stack is the one whose left subtree you just finished: pop it, emit it, and continue with its right subtree.
flowchart TD
S["cur = root, stack empty"] --> L{"cur or stack non-empty?"}
L -->|"no"| D["done"]
L -->|"yes"| C{"cur is null?"}
C -->|"no"| P["push cur<br/>cur = cur.left"]
P --> L
C -->|"yes"| Q["cur = pop<br/>emit cur.val<br/>cur = cur.right"]
Q --> L
Here is the loop run by hand on the 7-node tree with level order [4, 2, 6, 1, 3, 5, 7] (a BST, so the output comes out sorted). Each row is one iteration; the stack is written bottom to top. The table was produced by running the algorithm.
| Step | Action | cur after | Stack after | Output so far |
|---|---|---|---|---|
| 1 | push 4, go left | 2 | 4 | — |
| 2 | push 2, go left | 1 | 4, 2 | — |
| 3 | push 1, go left | null | 4, 2, 1 | — |
| 4 | pop 1, emit, go right | null | 4, 2 | 1 |
| 5 | pop 2, emit, go right | 3 | 4 | 1, 2 |
| 6 | push 3, go left | null | 4, 3 | 1, 2 |
| 7 | pop 3, emit, go right | null | 4 | 1, 2, 3 |
| 8 | pop 4, emit, go right | 6 | — | 1, 2, 3, 4 |
| 9 | push 6, go left | 5 | 6 | 1, 2, 3, 4 |
| 10 | push 5, go left | null | 6, 5 | 1, 2, 3, 4 |
| 11 | pop 5, emit, go right | null | 6 | 1, 2, 3, 4, 5 |
| 12 | pop 6, emit, go right | 7 | — | 1, 2, 3, 4, 5, 6 |
| 13 | push 7, go left | null | 7 | 1, 2, 3, 4, 5, 6 |
| 14 | pop 7, emit, go right | null | — | 1, 2, 3, 4, 5, 6, 7 |
Exactly iterations: every node is pushed once and popped once. Notice what the stack contains at every moment: the nodes on the path from the root to cur whose left subtree is in progress, in root-to-leaf order. That is the invariant the correctness proof uses.
The loop can be paused: an object whose next() runs it to the next emit is a BST iterator with memory and amortized per call, used again in Binary Search Trees.
Iterative postorder: two stacks, one stack, and a reversal
Postorder is the awkward one: a node must wait until both subtrees are done, so when you look at the top of the stack you need to know whether you are arriving from the left or returning from the right. Three standard ways out:
Two stacks (or: reversed modified preorder). Do a preorder that visits node, right, left (push left before right), writing into a second stack. Reading that second stack from the top gives left, right, node — postorder. On the example tree the modified preorder is 1, 3, 6, 2, 5, 8, 7, 4, and its reverse is 4, 7, 8, 5, 2, 6, 3, 1, which is the postorder.
def postorder_two_stacks(root):
if root is None:
return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node) # node, then right, then left ...
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return [n.val for n in reversed(s2)] # ... reversed = left, right, node
class T:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
ex = T(1, T(2, T(4), T(5, T(7), T(8))), T(3, None, T(6)))
assert postorder_two_stacks(ex) == [4, 7, 8, 5, 2, 6, 3, 1]
assert postorder_two_stacks(None) == []
Simple and hard to get wrong, but it stores all nodes in s2, so it is space even for a balanced tree, and it cannot stream: nothing is emitted until the end.
One stack with a prev pointer. Run the go-left loop, but peek when cur is null. If the top has a right child that is not prev (the node emitted last), go right; otherwise pop, emit, and set prev. space, and it streams. The test works because a subtree's postorder ends with its root, so returning from the right means prev is top.right.
Unified "visited flag" template. Push pairs (node, expanded). When you pop a pair with expanded = false, push its pieces back in the reverse of the order you want them processed, with the node itself marked expanded = true. When you pop a pair with expanded = true, emit it. One loop does all three orders; only the push order changes.
def traverse(root, order: str) -> list[int]:
out, stack = [], [(root, False)]
while stack:
node, expanded = stack.pop()
if node is None:
continue
if expanded:
out.append(node.val)
elif order == "pre": # want: node, left, right -> push reversed
stack += [(node.right, False), (node.left, False), (node, True)]
elif order == "in": # want: left, node, right
stack += [(node.right, False), (node, True), (node.left, False)]
else: # want: left, right, node
stack += [(node, True), (node.right, False), (node.left, False)]
return out
class T:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
ex = T(1, T(2, T(4), T(5, T(7), T(8))), T(3, None, T(6)))
assert traverse(ex, "pre") == [1, 2, 4, 5, 7, 8, 3, 6]
assert traverse(ex, "in") == [4, 2, 7, 5, 8, 1, 3, 6]
assert traverse(ex, "post") == [4, 7, 8, 5, 2, 6, 3, 1]
assert traverse(None, "in") == []
The template simulates the recursive function: expanded = false is a call not yet started, expanded = true is the point in its body where it appends. It does about twice the stack work of the specialised loops, but it is one thing to remember, and it is the template for turning any recursive tree DP iterative.
Level order, with levels
Breadth-first search on a tree needs no visited set, because a tree has no cycles and every node is reached from exactly one parent. Put the root in a queue; repeatedly dequeue a node, emit it, enqueue its non-null children.
To know where one level ends and the next begins, snapshot the queue length at the start of each round: exactly that many nodes belong to the current level, and everything enqueued while processing them belongs to the next. This level-size snapshot is the single most reused trick in tree BFS: right side view (last node of each level), level averages, minimum depth (first level that contains a leaf), maximum width, "connect next-right pointers" all use it.
# fragment — level order with level boundaries
from collections import deque
def levels(root):
out, q = [], deque([root] if root else [])
while q:
level = []
for _ in range(len(q)): # snapshot: only this level's nodes
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
out.append(level)
return out
The queue holds about one level, so space is for maximum width . A perfect tree has , so BFS needs memory where DFS needs ; on a path it is the reverse. The shape decides.
Zigzag order alternates direction per level: run the level-size BFS and reverse the odd levels.
Vertical order
Give the root column 0; a left child gets its parent's column minus one, a right child plus one. Vertical order lists columns from leftmost to rightmost. The subtle part is the order within a column, and there are two common specifications:
- By depth, ties in BFS order (LeetCode 314): a BFS appending to
columns[c]produces this directly. - By depth, ties by value (LeetCode 987): collect
(column, row, value)triples and sort.
On the example tree the columns are : [4], : [2, 7], : [1, 5], : [3, 8], : [6]. On the perfect tree 1..7, column 0 holds 1 at depth 0 and both 5 and 6 at depth 2 — that collision is where the two specifications differ.
from collections import defaultdict, deque
def vertical_order(root, sort_ties_by_value: bool) -> list[list[int]]:
cols = defaultdict(list) # col -> [(row, seq, val)]
q, seq = deque([(root, 0, 0)] if root else []), 0
while q:
node, row, col = q.popleft()
cols[col].append((row, node.val if sort_ties_by_value else seq, node.val))
seq += 1
if node.left: q.append((node.left, row + 1, col - 1))
if node.right: q.append((node.right, row + 1, col + 1))
return [[v for _, _, v in sorted(cols[c])] for c in sorted(cols)]
class T:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
ex = T(1, T(2, T(4), T(5, T(7), T(8))), T(3, None, T(6)))
assert vertical_order(ex, True) == [[4], [2, 7], [1, 5], [3, 8], [6]]
perfect = T(1, T(2, T(4), T(6)), T(3, T(5), T(7))) # 6 and 5 collide at row 2, col 0
assert vertical_order(perfect, False) == [[4], [2], [1, 6, 5], [3], [7]] # BFS order
assert vertical_order(perfect, True) == [[4], [2], [1, 5, 6], [3], [7]] # by value
Top and bottom views keep only the first or last node per column (next lesson). Columns are at most consecutive integers, so an offset array replaces the column sort: for the 314 rule, for 987 because of the tie sort.
Morris traversal: O(1) extra space
Every traversal so far remembers its way back in a stack or queue. Morris remembers it inside the tree, in the null pointers.
At a node cur with a left subtree, the node visited just before cur in inorder is its inorder predecessor, the rightmost node of the left subtree, whose right pointer is null. Before descending left, point it at cur: a thread. When the left subtree is finished, going right from the predecessor follows the thread back to cur. On that second arrival the thread is found, removed, cur is emitted, and the walk moves right.
cur = root
while cur is not null:
if cur.left is null:
emit cur; cur = cur.right # nothing on the left: visit, go right
else:
pred = rightmost node of cur.left, stopping if pred.right == cur
if pred.right is null: # first arrival at cur
pred.right = cur; cur = cur.left # thread, then go left
else: # second arrival, via the thread
pred.right = null; emit cur; cur = cur.right # unthread, visit, go right
On the example tree:
flowchart TD
n1((1)) --> n2((2))
n1 --> n3((3))
n2 --> n4((4))
n2 --> n5((5))
n3 --> n6((6))
n5 --> n7((7))
n5 --> n8((8))
n4 -.->|"thread"| n2
n7 -.->|"thread"| n5
n8 -.->|"thread"| n1
The dotted edges are the threads Morris creates; at most one per node with a left child, and every one is removed before the traversal ends. The full run, produced by script:
| Step | cur | Situation | Action | Emitted |
|---|---|---|---|---|
| 1 | 1 | predecessor 8, no thread | thread 8 → 1, go left | — |
| 2 | 2 | predecessor 4, no thread | thread 4 → 2, go left | — |
| 3 | 4 | no left child | emit, go right (the thread) | 4 |
| 4 | 2 | predecessor 4 already threads to 2 | unthread, emit, go right | 2 |
| 5 | 5 | predecessor 7, no thread | thread 7 → 5, go left | — |
| 6 | 7 | no left child | emit, follow thread | 7 |
| 7 | 5 | predecessor 7 threads to 5 | unthread, emit, go right | 5 |
| 8 | 8 | no left child | emit, follow thread | 8 |
| 9 | 1 | predecessor 8 threads to 1 | unthread, emit, go right | 1 |
| 10 | 3 | no left child | emit, go right | 3 |
| 11 | 6 | no left child | emit, go right (null: stop) | 6 |
Output 4, 2, 7, 5, 8, 1, 3, 6 — the inorder — and every thread created in steps 1, 2, 5 was removed in steps 9, 4, 7.
Morris preorder moves the emit to the first arrival (when the thread is created); nodes without a left child are still emitted on arrival. A Morris postorder exists (emit each left subtree's right spine reversed when its thread is removed) but is fiddly and rarely worth it.
Morris mutates the tree while it runs
The tree is restored when the loop finishes, but during the run it contains cycles. Never run it on a tree another thread reads, never break out early without removing the remaining threads, and never use it on immutable or shared structures.
Serialization and deserialization
Serialization flattens a tree so that deserialization can rebuild it exactly. A bare traversal is not enough (preorder 1, 2 fits 2 as either child), so record the empty subtrees too.
Preorder with null markers. Emit the value for a node and a marker such as # for every null child pointer. The example tree serializes as
1,2,4,#,#,5,7,#,#,8,#,#,3,#,6,#,#
which has 8 values and 9 markers, as the null-pointer theorem promises. To deserialize, read tokens left to right with a recursive function: a # returns null; a value creates a node whose left subtree is "deserialize the rest" and whose right subtree is "deserialize what remains after that". The proof that this always reconstructs exactly the original tree, and that no two trees share a serialization, is in the Correctness section.
Level order with null markers. Emit nodes in BFS order, writing a marker for each null child of a real node. The example becomes
1,2,3,4,5,#,6,#,#,7,8,#,#,#,#,#,#
(LeetCode's display format drops the trailing markers). Decode with the same queue-based builder. Level order is iterative on both sides, so it never overflows a stack; preorder streams and decodes in one recursive-descent pass.
Inorder with null markers is not a serialization. It always alternates marker, value, marker, …, marker, so every tree with the same inorder values encodes identically: inorder never says where the root is.
Construction from two traversals
Preorder + inorder → tree (values distinct). Preorder's first element is the root . Find in the inorder sequence at position ; everything to the left of is the left subtree's inorder, of size , and everything to the right is the right subtree's. In preorder, after , the next elements are the left subtree's preorder and the rest are the right subtree's. Recurse on both halves.
flowchart TD
A["pre 1 2 4 5 7 8 3 6<br/>in 4 2 7 5 8 1 3 6"] -->|"root 1 at in-index 5, left size 5"| B["pre 2 4 5 7 8<br/>in 4 2 7 5 8"]
A --> C["pre 3 6<br/>in 3 6"]
B -->|"root 2, left size 1"| D["pre 4 / in 4"]
B --> E["pre 5 7 8<br/>in 7 5 8"]
C -->|"root 3, left size 0"| F["pre 6 / in 6"]
E --> G["7"]
E --> H["8"]
Scanning for costs on a skewed tree; a value-to-index hash map plus index ranges instead of slices makes it . A map-free version follows the implementation.
Postorder + inorder → tree. Mirror image: postorder's last element is the root. If you consume postorder from the end, you meet the root, then the right subtree's nodes, then the left's — so build the right subtree first.
Preorder + postorder is ambiguous. Take the two-node trees "1 with left child 2" and "1 with right child 2". Both have preorder 1, 2 and postorder 2, 1. In general, whenever a node has exactly one child, preorder and postorder cannot tell which side that child is on, because both orders put the child's block in the same place relative to the parent. A brute-force enumeration over all small trees confirms the exact count: the number of trees consistent with a given preorder and postorder is , where is the number of nodes with exactly one child. For a full binary tree () the pair is unique: the element after the root in preorder is the left child's root, its position in postorder tells you the left subtree's size, and you recurse. LeetCode 889 asks for "any" valid tree for this reason.
Counting binary trees: the Catalan numbers
How many structurally different binary trees have nodes? Call it . The empty tree is the only tree with 0 nodes, so . A tree with nodes is a root plus a left subtree with nodes and a right subtree with nodes, for some from to , and the two subtrees can be chosen independently:
The first values are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 for (checked by enumerating every shape), and they grow like . , so "try every tree shape" is hopeless beyond tiny .
The same numbers count BSTs on keys (pick root ; smaller keys go left, larger right — the same recurrence), full binary trees with leaves, parenthesizations of factors and balanced bracket strings of length . With distinct labels placed freely there are trees: 60,949,324,800 for .
from functools import cache
from math import comb
@cache
def catalan(n: int) -> int:
return 1 if n == 0 else sum(catalan(k) * catalan(n - 1 - k) for k in range(n))
assert [catalan(n) for n in range(11)] == [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]
assert all(catalan(n) == comb(2 * n, n) // (n + 1) for n in range(30))
That memoised recurrence is your first taste of interval-style dynamic programming; Module 6 returns to it.
The ladder: brute force → better → optimal
Two ladders, because this page has two central problems: visiting every node, and rebuilding a tree.
Ladder 1: inorder traversal, by extra space
Rung 1 — recursion. time, on the runtime's fixed-size call stack; a -node path overflows it.
Rung 2 — explicit stack. Same bounds, but the stack lives on the heap and the loop can pause between emits. The production default.
Rung 3 — parent pointers. Successor = leftmost node of the right subtree, else the first ancestor reached from a left child. extra space per traversal and time (each edge walked down and up once), paid for by a permanent pointer per node.
Rung 4 — Morris. extra space with no extra fields and time, but it temporarily mutates the tree and does two to three times the pointer work.
| Rung | Time | Extra space | Mutates tree | Pausable | Use when |
|---|---|---|---|---|---|
| Recursion | call stack | no | no (without generators) | Height is known to be small | |
| Explicit stack | heap | no | yes | Default; iterators; unknown shape | |
| Parent pointers | per traversal, stored | no | yes | The tree already stores parents | |
| Morris | temporarily | no | Memory is the binding constraint, single-threaded |
Ladder 2: build from preorder + inorder
Rung 1 — slice and scan. Find the root in the inorder list by linear search, slice both lists, recurse. Each level of recursion copies and scans its slice, so the cost is on a skewed tree (and on a balanced one).
Rung 2 — index ranges plus a hash map. Precompute pos[value] = inorder index; pass (lo, hi) bounds instead of slices and keep one moving index into preorder. Each node costs : time, space for the map and for recursion.
Rung 3 — no map, bound-driven. Consume preorder left to right and inorder left to right simultaneously, passing a "stop" value (the ancestor whose left subtree you are building). A subtree ends when the next inorder value equals the stop value. time and only extra space — no hash map. This is the version to know when values are large objects you would rather not hash.
| Rung | Time | Extra space | Needs distinct values |
|---|---|---|---|
| Slice and scan | worst | worst in copies | yes |
| Ranges + hash map | yes | ||
| Stop-value, no map | yes |
Correctness
Iterative inorder
Invariant. At the top of each loop iteration: (a) the output is the inorder sequence of exactly the nodes already emitted, in order; (b) the stack, bottom to top, holds nodes that are exactly the nodes which still need emitting and whose left subtree is either finished or is the subtree containing cur; (c) the nodes still to be emitted are, in inorder, "all of subtree(cur)", then , then right-subtree(), then , then right-subtree(), …, then , then right-subtree().
Initialisation. Stack empty, cur = root: (c) says "all of the tree remains", true.
Push step (cur not null). Inorder of subtree(cur) is inorder(left), cur, inorder(right). Pushing cur and moving to cur.left rewrites the head of the remaining sequence as subtree(cur.left), then the new top cur, then right-subtree(cur) — exactly the form (c) requires.
Pop step (cur null). Subtree(null) is empty, so by (c) the next node in inorder is . Emitting it maintains (a). Setting cur = s_k.right makes the remaining sequence start with subtree(cur), followed by and so on — (c) again.
Termination. When cur is null and the stack is empty, (c) says nothing remains, so by (a) the output is the complete inorder. Each node is pushed exactly once (when cur first reaches it) and popped once, so the loop runs exactly times.
Morris traversal: restores the tree and visits in inorder
Consider any node with a non-null left subtree. Let be its inorder predecessor, the rightmost node of ; is null in the original tree.
- The first time
curreaches , the predecessor search walks right from . It stops at with null, because no thread into exists yet. The algorithm sets and descends left. - The traversal of 's subtree only ever moves into that subtree or along threads created inside it, until it reaches and moves right from — which, through the thread, returns to . (Inductively, the subtree's own threads all point to nodes inside it, except the one at , which points to .)
- On this second arrival, the predecessor search walks the same right spine and stops at because . The algorithm resets to null, emits and moves to .
So every thread is created once and removed once, and the tree ends unchanged. Between steps 1 and 3 exactly the left subtree of is emitted, then , then the right subtree begins — the inorder definition; nodes without a left child are emitted on arrival, which also matches.
Why the time is even though there is an inner loop. The inner loop walks the edge and then the right spine below it, twice per node with a left child. A right edge belongs to at most one such spine (climb from it through right-child links; the node above the first left-child link is the only candidate ), and a left edge starts only its own parent's search. So the searches walk each tree edge at most twice: at most steps. cur itself moves at most twice per node. Altogether fewer than pointer steps; random trees in a test script never exceeded .
Preorder with null markers is a unique encoding
Let and for a tree with root value and subtrees , .
Lemma (counting). In the number of markers is one more than the number of values, and every proper prefix has at most as many markers as values. Proof by induction on the tree. For : one marker, no values, and the only proper prefix is empty. For : values and markers , one more. A proper prefix is either alone (1 value, 0 markers), or plus a proper prefix of (surplus of values ), or (values and markers equal), or plus a proper prefix of (values markers).
Theorem. is injective, and the recursive decoder inverts it. Proof by strong induction on the length of the string. If the first token is , the tree is empty. Otherwise the first token is the root's value, and the rest must split as . By the lemma, ends at the first position where markers exceed values in the rest of the string — no shorter piece can be a complete encoding, and no longer piece can either, since any complete encoding's own prefixes never reach the surplus. So the split point is forced, and are determined by the induction hypothesis, and the decoder, which reads exactly one complete encoding for the left subtree before starting the right, finds that same split.
The lemma doubles as a validator that never builds the tree: scan tokens with a counter of open slots, starting at 1; each token fills a slot (decrement), each value opens two (increment by 2); the string is valid iff the counter never hits 0 before the last token and ends at exactly 0. That is LeetCode 331.
Level order with null markers is a unique encoding
The decoder keeps a queue of nodes whose children have not been assigned and consumes two tokens per dequeued node. The encoder emits, in BFS order, each real node's value and, for each real node, its two child slots in the order the BFS meets them. By induction on the token index, the -th token the decoder reads is placed in the same child slot of the same node from which the encoder emitted it: both process real nodes in the same FIFO order, and both handle exactly two slots per real node. So , which forces to be injective.
Preorder + inorder determines the tree
Claim. If all values are distinct, at most one binary tree has a given preorder and inorder , and the construction algorithm builds it. Proof by strong induction on . For both are empty. Otherwise the root is (preorder starts with the root). Since values are distinct, occurs once in , at index , and by the inorder definition is the left subtree's inorder and the right's, so the left subtree has nodes. By the preorder definition, is the left subtree's preorder and the right's. Both pairs describe strictly smaller trees, which by induction are unique and correctly built.
Distinctness is essential: with values [1, 1], "1 with left child 1" and "1 with right child 1" both have preorder 1, 1 and inorder 1, 1. The postorder + inorder proof is the mirror image. Preorder + postorder fails at the step "the left subtree has nodes": if the root has one child, nothing tells you whether that child's block is a left or right subtree.
Complexity
| Operation | Time | Extra space | Notes |
|---|---|---|---|
| Recursive pre/in/post | call stack | calls | |
| Iterative preorder / inorder | exactly pushes and pops | ||
| Two-stack postorder | second stack holds every node | ||
| One-stack postorder | |||
| Visited-flag template | about pushes including null children | ||
| Level order (with levels, zigzag) | , | queue holds about one level | |
| Vertical order | / | 314 rule / 987 rule (tie sort) | |
| Morris inorder / preorder | , fewer than pointer steps | writes pointers per node with a left child | |
| Serialize / deserialize | output, or working | tokens | |
| Build from pre+in or post+in | map + | naive scan: |
Best, average and worst case coincide: every node must be visited, so is a lower bound and every algorithm here meets it. Space depends on shape. A BST built from a random permutation has expected height about (Devroye 1986; Reed 2003), so stack-based traversals use logarithmic space on typical inputs and linear space only on adversarial ones.
On constants: when the tree is much larger than cache, each pointer step is a likely miss (order of 100 ns from DRAM) versus a few nanoseconds per element of an array scan, so traversing a large, randomly allocated tree can be one to two orders of magnitude slower than scanning an array of the same size. Arena allocation in traversal order helps; Morris, which also writes to the tree, is chosen for space, not speed; the array layout of complete trees is the cache-friendly extreme.
Implementation
The two code groups below are complete and self-checking. Each builds trees from LeetCode-style level-order arrays with nulls and asserts the sequences in the table above. The first covers all traversals; the second covers serialization and construction.
from collections import deque
class TreeNode:
def __init__(self, val: int):
self.val = val
self.left: "TreeNode | None" = None
self.right: "TreeNode | None" = None
def build(level: list[int | None]) -> TreeNode | None:
"""Build from LeetCode level order: None marks a missing child of an existing node."""
if not level or level[0] is None:
return None
root = TreeNode(level[0])
q, i = deque([root]), 1
while q and i < len(level):
node = q.popleft()
if i < len(level) and level[i] is not None:
node.left = TreeNode(level[i])
q.append(node.left)
i += 1
if i < len(level) and level[i] is not None:
node.right = TreeNode(level[i])
q.append(node.right)
i += 1
return root
def preorder_rec(root):
out = []
def go(n):
if n:
out.append(n.val); go(n.left); go(n.right)
go(root)
return out
def inorder_rec(root):
out = []
def go(n):
if n:
go(n.left); out.append(n.val); go(n.right)
go(root)
return out
def postorder_rec(root):
out = []
def go(n):
if n:
go(n.left); go(n.right); out.append(n.val)
go(root)
return out
def preorder_iter(root):
out, stack = [], [root] if root else []
while stack:
n = stack.pop()
out.append(n.val)
if n.right: stack.append(n.right)
if n.left: stack.append(n.left)
return out
def inorder_iter(root):
out, stack, cur = [], [], root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
out.append(cur.val)
cur = cur.right
return out
def postorder_iter(root):
out, stack, cur, prev = [], [], root, None
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
top = stack[-1]
if top.right and top.right is not prev:
cur = top.right # right subtree not done yet
else:
out.append(top.val) # both subtrees done
prev = stack.pop()
return out
def level_order(root):
out, q = [], deque([root] if root else [])
while q:
level = []
for _ in range(len(q)):
n = q.popleft()
level.append(n.val)
if n.left: q.append(n.left)
if n.right: q.append(n.right)
out.append(level)
return out
def zigzag(root):
return [lv if d % 2 == 0 else lv[::-1] for d, lv in enumerate(level_order(root))]
def morris_inorder(root):
out, cur = [], root
while cur:
if cur.left is None:
out.append(cur.val)
cur = cur.right
else:
pred = cur.left
while pred.right and pred.right is not cur:
pred = pred.right
if pred.right is None:
pred.right = cur # thread
cur = cur.left
else:
pred.right = None # unthread
out.append(cur.val)
cur = cur.right
return out
def morris_preorder(root):
out, cur = [], root
while cur:
if cur.left is None:
out.append(cur.val)
cur = cur.right
else:
pred = cur.left
while pred.right and pred.right is not cur:
pred = pred.right
if pred.right is None:
out.append(cur.val) # emit on first arrival
pred.right = cur
cur = cur.left
else:
pred.right = None
cur = cur.right
return out
if __name__ == "__main__":
t = build([1, 2, 3, 4, 5, None, 6, None, None, 7, 8])
PRE, IN, POST = [1, 2, 4, 5, 7, 8, 3, 6], [4, 2, 7, 5, 8, 1, 3, 6], [4, 7, 8, 5, 2, 6, 3, 1]
assert preorder_rec(t) == preorder_iter(t) == morris_preorder(t) == PRE
assert inorder_rec(t) == inorder_iter(t) == morris_inorder(t) == IN
assert postorder_rec(t) == postorder_iter(t) == POST
assert level_order(t) == [[1], [2, 3], [4, 5, 6], [7, 8]]
assert zigzag(t) == [[1], [3, 2], [4, 5, 6], [8, 7]]
assert inorder_rec(t) == IN # Morris left the tree intact
assert inorder_iter(build([4, 2, 6, 1, 3, 5, 7])) == [1, 2, 3, 4, 5, 6, 7]
e = build([])
assert preorder_iter(e) == inorder_iter(e) == postorder_iter(e) == morris_inorder(e) == []
assert level_order(e) == []
print("all traversal checks passed")
import java.util.*;
public class Traversals {
static final class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
// LeetCode level order: null marks a missing child of an existing node.
static TreeNode build(Integer[] level) {
if (level.length == 0 || level[0] == null) return null;
TreeNode root = new TreeNode(level[0]);
ArrayDeque<TreeNode> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < level.length) {
TreeNode node = q.poll();
if (i < level.length && level[i] != null) { node.left = new TreeNode(level[i]); q.add(node.left); }
i++;
if (i < level.length && level[i] != null) { node.right = new TreeNode(level[i]); q.add(node.right); }
i++;
}
return root;
}
static void pre(TreeNode n, List<Integer> out) { if (n == null) return; out.add(n.val); pre(n.left, out); pre(n.right, out); }
static void in(TreeNode n, List<Integer> out) { if (n == null) return; in(n.left, out); out.add(n.val); in(n.right, out); }
static void post(TreeNode n, List<Integer> out) { if (n == null) return; post(n.left, out); post(n.right, out); out.add(n.val); }
static List<Integer> preorderIter(TreeNode root) {
List<Integer> out = new ArrayList<>();
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode n = stack.pop();
out.add(n.val);
if (n.right != null) stack.push(n.right);
if (n.left != null) stack.push(n.left);
}
return out;
}
static List<Integer> inorderIter(TreeNode root) {
List<Integer> out = new ArrayList<>();
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
if (cur != null) { stack.push(cur); cur = cur.left; }
else { cur = stack.pop(); out.add(cur.val); cur = cur.right; }
}
return out;
}
static List<Integer> postorderIter(TreeNode root) {
List<Integer> out = new ArrayList<>();
ArrayDeque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root, prev = null;
while (cur != null || !stack.isEmpty()) {
while (cur != null) { stack.push(cur); cur = cur.left; }
TreeNode top = stack.peek();
if (top.right != null && top.right != prev) cur = top.right;
else { out.add(top.val); prev = stack.pop(); }
}
return out;
}
static List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> out = new ArrayList<>();
ArrayDeque<TreeNode> q = new ArrayDeque<>();
if (root != null) q.add(root);
while (!q.isEmpty()) {
List<Integer> level = new ArrayList<>();
for (int k = q.size(); k > 0; k--) {
TreeNode n = q.poll();
level.add(n.val);
if (n.left != null) q.add(n.left);
if (n.right != null) q.add(n.right);
}
out.add(level);
}
return out;
}
static List<List<Integer>> zigzag(TreeNode root) {
List<List<Integer>> levels = levelOrder(root);
for (int d = 1; d < levels.size(); d += 2) Collections.reverse(levels.get(d));
return levels;
}
static List<Integer> morrisInorder(TreeNode root) {
List<Integer> out = new ArrayList<>();
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) { out.add(cur.val); cur = cur.right; continue; }
TreeNode pred = cur.left;
while (pred.right != null && pred.right != cur) pred = pred.right;
if (pred.right == null) { pred.right = cur; cur = cur.left; }
else { pred.right = null; out.add(cur.val); cur = cur.right; }
}
return out;
}
static List<Integer> morrisPreorder(TreeNode root) {
List<Integer> out = new ArrayList<>();
TreeNode cur = root;
while (cur != null) {
if (cur.left == null) { out.add(cur.val); cur = cur.right; continue; }
TreeNode pred = cur.left;
while (pred.right != null && pred.right != cur) pred = pred.right;
if (pred.right == null) { out.add(cur.val); pred.right = cur; cur = cur.left; }
else { pred.right = null; cur = cur.right; }
}
return out;
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
TreeNode t = build(new Integer[]{1, 2, 3, 4, 5, null, 6, null, null, 7, 8});
List<Integer> PRE = List.of(1, 2, 4, 5, 7, 8, 3, 6), IN = List.of(4, 2, 7, 5, 8, 1, 3, 6),
POST = List.of(4, 7, 8, 5, 2, 6, 3, 1);
List<Integer> a = new ArrayList<>(), b = new ArrayList<>(), c = new ArrayList<>();
pre(t, a); in(t, b); post(t, c);
check(a.equals(PRE) && preorderIter(t).equals(PRE) && morrisPreorder(t).equals(PRE), "preorder");
check(b.equals(IN) && inorderIter(t).equals(IN) && morrisInorder(t).equals(IN), "inorder");
check(c.equals(POST) && postorderIter(t).equals(POST), "postorder");
check(levelOrder(t).equals(List.of(List.of(1), List.of(2, 3), List.of(4, 5, 6), List.of(7, 8))), "levels");
check(zigzag(t).equals(List.of(List.of(1), List.of(3, 2), List.of(4, 5, 6), List.of(8, 7))), "zigzag");
check(inorderIter(t).equals(IN), "Morris restored the tree");
check(inorderIter(build(new Integer[]{4, 2, 6, 1, 3, 5, 7})).equals(List.of(1, 2, 3, 4, 5, 6, 7)), "bst");
TreeNode e = build(new Integer[]{});
check(preorderIter(e).isEmpty() && inorderIter(e).isEmpty() && postorderIter(e).isEmpty()
&& morrisInorder(e).isEmpty() && levelOrder(e).isEmpty(), "empty");
System.out.println("all traversal checks passed");
}
}
#include <algorithm>
#include <cassert>
#include <deque>
#include <iostream>
#include <optional>
#include <queue>
#include <vector>
struct TreeNode {
int val;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
explicit TreeNode(int v) : val(v) {}
};
std::deque<TreeNode> arena; // owns every node; deque never moves existing elements
TreeNode* make(int v) { arena.emplace_back(v); return &arena.back(); }
// LeetCode level order: nullopt marks a missing child of an existing node.
TreeNode* build(const std::vector<std::optional<int>>& level) {
if (level.empty() || !level[0]) return nullptr;
TreeNode* root = make(*level[0]);
std::queue<TreeNode*> q;
q.push(root);
size_t i = 1;
while (!q.empty() && i < level.size()) {
TreeNode* node = q.front(); q.pop();
if (i < level.size() && level[i]) { node->left = make(*level[i]); q.push(node->left); }
++i;
if (i < level.size() && level[i]) { node->right = make(*level[i]); q.push(node->right); }
++i;
}
return root;
}
void pre(TreeNode* n, std::vector<int>& out) { if (!n) return; out.push_back(n->val); pre(n->left, out); pre(n->right, out); }
void in(TreeNode* n, std::vector<int>& out) { if (!n) return; in(n->left, out); out.push_back(n->val); in(n->right, out); }
void post(TreeNode* n, std::vector<int>& out) { if (!n) return; post(n->left, out); post(n->right, out); out.push_back(n->val); }
std::vector<int> preorderIter(TreeNode* root) {
std::vector<int> out;
std::vector<TreeNode*> stack;
if (root) stack.push_back(root);
while (!stack.empty()) {
TreeNode* n = stack.back(); stack.pop_back();
out.push_back(n->val);
if (n->right) stack.push_back(n->right);
if (n->left) stack.push_back(n->left);
}
return out;
}
std::vector<int> inorderIter(TreeNode* root) {
std::vector<int> out;
std::vector<TreeNode*> stack;
TreeNode* cur = root;
while (cur || !stack.empty()) {
if (cur) { stack.push_back(cur); cur = cur->left; }
else { cur = stack.back(); stack.pop_back(); out.push_back(cur->val); cur = cur->right; }
}
return out;
}
std::vector<int> postorderIter(TreeNode* root) {
std::vector<int> out;
std::vector<TreeNode*> stack;
TreeNode *cur = root, *prev = nullptr;
while (cur || !stack.empty()) {
while (cur) { stack.push_back(cur); cur = cur->left; }
TreeNode* top = stack.back();
if (top->right && top->right != prev) cur = top->right;
else { out.push_back(top->val); prev = top; stack.pop_back(); }
}
return out;
}
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> out;
std::queue<TreeNode*> q;
if (root) q.push(root);
while (!q.empty()) {
std::vector<int> level;
for (size_t k = q.size(); k > 0; --k) {
TreeNode* n = q.front(); q.pop();
level.push_back(n->val);
if (n->left) q.push(n->left);
if (n->right) q.push(n->right);
}
out.push_back(std::move(level));
}
return out;
}
std::vector<std::vector<int>> zigzag(TreeNode* root) {
auto levels = levelOrder(root);
for (size_t d = 1; d < levels.size(); d += 2) std::reverse(levels[d].begin(), levels[d].end());
return levels;
}
std::vector<int> morrisInorder(TreeNode* root) {
std::vector<int> out;
TreeNode* cur = root;
while (cur) {
if (!cur->left) { out.push_back(cur->val); cur = cur->right; continue; }
TreeNode* pred = cur->left;
while (pred->right && pred->right != cur) pred = pred->right;
if (!pred->right) { pred->right = cur; cur = cur->left; }
else { pred->right = nullptr; out.push_back(cur->val); cur = cur->right; }
}
return out;
}
std::vector<int> morrisPreorder(TreeNode* root) {
std::vector<int> out;
TreeNode* cur = root;
while (cur) {
if (!cur->left) { out.push_back(cur->val); cur = cur->right; continue; }
TreeNode* pred = cur->left;
while (pred->right && pred->right != cur) pred = pred->right;
if (!pred->right) { out.push_back(cur->val); pred->right = cur; cur = cur->left; }
else { pred->right = nullptr; cur = cur->right; }
}
return out;
}
int main() {
using std::nullopt;
TreeNode* t = build({1, 2, 3, 4, 5, nullopt, 6, nullopt, nullopt, 7, 8});
const std::vector<int> PRE{1, 2, 4, 5, 7, 8, 3, 6}, IN{4, 2, 7, 5, 8, 1, 3, 6}, POST{4, 7, 8, 5, 2, 6, 3, 1};
std::vector<int> a, b, c;
pre(t, a); in(t, b); post(t, c);
assert(a == PRE && preorderIter(t) == PRE && morrisPreorder(t) == PRE);
assert(b == IN && inorderIter(t) == IN && morrisInorder(t) == IN);
assert(c == POST && postorderIter(t) == POST);
assert((levelOrder(t) == std::vector<std::vector<int>>{{1}, {2, 3}, {4, 5, 6}, {7, 8}}));
assert((zigzag(t) == std::vector<std::vector<int>>{{1}, {3, 2}, {4, 5, 6}, {8, 7}}));
assert(inorderIter(t) == IN); // Morris restored the tree
assert((inorderIter(build({4, 2, 6, 1, 3, 5, 7})) == std::vector<int>{1, 2, 3, 4, 5, 6, 7}));
TreeNode* e = build({});
assert(preorderIter(e).empty() && inorderIter(e).empty() && postorderIter(e).empty());
assert(morrisInorder(e).empty() && levelOrder(e).empty());
std::cout << "all traversal checks passed\n";
}
class TreeNode {
val: number;
left: TreeNode | null = null;
right: TreeNode | null = null;
constructor(val: number) {
this.val = val;
}
}
// LeetCode level order: null marks a missing child of an existing node.
function build(level: (number | null)[]): TreeNode | null {
if (level.length === 0 || level[0] === null) return null;
const root = new TreeNode(level[0]);
const q: TreeNode[] = [root];
let head = 0;
let i = 1;
while (head < q.length && i < level.length) {
const node = q[head++];
const l = level[i++];
if (l !== null && l !== undefined) { node.left = new TreeNode(l); q.push(node.left); }
const r = i < level.length ? level[i] : null;
i++;
if (r !== null && r !== undefined) { node.right = new TreeNode(r); q.push(node.right); }
}
return root;
}
function preRec(n: TreeNode | null, out: number[] = []): number[] {
if (n) { out.push(n.val); preRec(n.left, out); preRec(n.right, out); }
return out;
}
function inRec(n: TreeNode | null, out: number[] = []): number[] {
if (n) { inRec(n.left, out); out.push(n.val); inRec(n.right, out); }
return out;
}
function postRec(n: TreeNode | null, out: number[] = []): number[] {
if (n) { postRec(n.left, out); postRec(n.right, out); out.push(n.val); }
return out;
}
function preorderIter(root: TreeNode | null): number[] {
const out: number[] = [];
const stack: TreeNode[] = root ? [root] : [];
while (stack.length) {
const n = stack.pop()!;
out.push(n.val);
if (n.right) stack.push(n.right);
if (n.left) stack.push(n.left);
}
return out;
}
function inorderIter(root: TreeNode | null): number[] {
const out: number[] = [];
const stack: TreeNode[] = [];
let cur = root;
while (cur || stack.length) {
if (cur) { stack.push(cur); cur = cur.left; }
else { const n = stack.pop()!; out.push(n.val); cur = n.right; }
}
return out;
}
function postorderIter(root: TreeNode | null): number[] {
const out: number[] = [];
const stack: TreeNode[] = [];
let cur = root;
let prev: TreeNode | null = null;
while (cur || stack.length) {
while (cur) { stack.push(cur); cur = cur.left; }
const top = stack[stack.length - 1];
if (top.right && top.right !== prev) cur = top.right;
else { out.push(top.val); prev = stack.pop()!; }
}
return out;
}
function levelOrder(root: TreeNode | null): number[][] {
const out: number[][] = [];
let level: TreeNode[] = root ? [root] : [];
while (level.length) {
out.push(level.map((n) => n.val));
const next: TreeNode[] = [];
for (const n of level) {
if (n.left) next.push(n.left);
if (n.right) next.push(n.right);
}
level = next;
}
return out;
}
function zigzag(root: TreeNode | null): number[][] {
return levelOrder(root).map((lv, d) => (d % 2 === 0 ? lv : [...lv].reverse()));
}
function morrisInorder(root: TreeNode | null): number[] {
const out: number[] = [];
let cur = root;
while (cur) {
if (!cur.left) { out.push(cur.val); cur = cur.right; continue; }
let pred = cur.left;
while (pred.right && pred.right !== cur) pred = pred.right;
if (!pred.right) { pred.right = cur; cur = cur.left; }
else { pred.right = null; out.push(cur.val); cur = cur.right; }
}
return out;
}
function morrisPreorder(root: TreeNode | null): number[] {
const out: number[] = [];
let cur = root;
while (cur) {
if (!cur.left) { out.push(cur.val); cur = cur.right; continue; }
let pred = cur.left;
while (pred.right && pred.right !== cur) pred = pred.right;
if (!pred.right) { out.push(cur.val); pred.right = cur; cur = cur.left; }
else { pred.right = null; cur = cur.right; }
}
return out;
}
function assertEq(actual: unknown, expected: unknown, what: string): void {
if (JSON.stringify(actual) !== JSON.stringify(expected)) {
throw new Error(`${what}: got ${JSON.stringify(actual)}, want ${JSON.stringify(expected)}`);
}
}
const t = build([1, 2, 3, 4, 5, null, 6, null, null, 7, 8]);
const PRE = [1, 2, 4, 5, 7, 8, 3, 6], IN = [4, 2, 7, 5, 8, 1, 3, 6], POST = [4, 7, 8, 5, 2, 6, 3, 1];
for (const [got, name] of [[preRec(t), "preRec"], [preorderIter(t), "preIter"], [morrisPreorder(t), "morrisPre"]] as const) assertEq(got, PRE, name);
for (const [got, name] of [[inRec(t), "inRec"], [inorderIter(t), "inIter"], [morrisInorder(t), "morrisIn"]] as const) assertEq(got, IN, name);
assertEq(postRec(t), POST, "postRec");
assertEq(postorderIter(t), POST, "postIter");
assertEq(levelOrder(t), [[1], [2, 3], [4, 5, 6], [7, 8]], "levels");
assertEq(zigzag(t), [[1], [3, 2], [4, 5, 6], [8, 7]], "zigzag");
assertEq(inorderIter(t), IN, "Morris restored the tree");
assertEq(inorderIter(build([4, 2, 6, 1, 3, 5, 7])), [1, 2, 3, 4, 5, 6, 7], "bst");
const e = build([]);
assertEq([preorderIter(e), inorderIter(e), postorderIter(e), morrisInorder(e), levelOrder(e)], [[], [], [], [], []], "empty");
console.log("all traversal checks passed");
Serialization (both formats) and construction from traversals:
from collections import deque
class TreeNode:
def __init__(self, val: int):
self.val = val
self.left: "TreeNode | None" = None
self.right: "TreeNode | None" = None
def build(level):
if not level or level[0] is None:
return None
root = TreeNode(level[0])
q, i = deque([root]), 1
while q and i < len(level):
node = q.popleft()
if i < len(level) and level[i] is not None:
node.left = TreeNode(level[i]); q.append(node.left)
i += 1
if i < len(level) and level[i] is not None:
node.right = TreeNode(level[i]); q.append(node.right)
i += 1
return root
def serialize_pre(root) -> str:
out = []
def go(n):
if n is None:
out.append("#"); return
out.append(str(n.val)); go(n.left); go(n.right)
go(root)
return ",".join(out)
def deserialize_pre(data: str):
tokens = iter(data.split(","))
def go():
tok = next(tokens)
if tok == "#":
return None
node = TreeNode(int(tok))
node.left = go()
node.right = go()
return node
return go()
def serialize_level(root) -> str:
out, q = [], deque([root])
while q:
n = q.popleft()
if n is None:
out.append("#")
else:
out.append(str(n.val)); q.append(n.left); q.append(n.right)
return ",".join(out)
def deserialize_level(data: str):
tok = data.split(",")
return build([None if t == "#" else int(t) for t in tok])
def build_pre_in(pre: list[int], ino: list[int]):
pos = {v: i for i, v in enumerate(ino)}
idx = 0
def go(lo: int, hi: int): # builds the subtree whose inorder is ino[lo..hi]
nonlocal idx
if lo > hi:
return None
node = TreeNode(pre[idx]); idx += 1
m = pos[node.val]
node.left = go(lo, m - 1)
node.right = go(m + 1, hi)
return node
return go(0, len(ino) - 1)
def build_post_in(post: list[int], ino: list[int]):
pos = {v: i for i, v in enumerate(ino)}
idx = len(post) - 1
def go(lo: int, hi: int):
nonlocal idx
if lo > hi:
return None
node = TreeNode(post[idx]); idx -= 1
m = pos[node.val]
node.right = go(m + 1, hi) # right first: postorder read backwards is node, right, left
node.left = go(lo, m - 1)
return node
return go(0, len(ino) - 1)
if __name__ == "__main__":
t = build([1, 2, 3, 4, 5, None, 6, None, None, 7, 8])
s = serialize_pre(t)
assert s == "1,2,4,#,#,5,7,#,#,8,#,#,3,#,6,#,#"
assert s.count("#") == s.count(",") + 1 - s.count("#") + 1 # markers = values + 1
assert serialize_pre(deserialize_pre(s)) == s
lv = serialize_level(t)
assert lv == "1,2,3,4,5,#,6,#,#,7,8,#,#,#,#,#,#"
assert serialize_pre(deserialize_level(lv)) == s
pre, ino, post = [1, 2, 4, 5, 7, 8, 3, 6], [4, 2, 7, 5, 8, 1, 3, 6], [4, 7, 8, 5, 2, 6, 3, 1]
assert serialize_pre(build_pre_in(pre, ino)) == s
assert serialize_pre(build_post_in(post, ino)) == s
skew = build([1, None, 2, None, 3])
assert serialize_pre(skew) == "1,#,2,#,3,#,#"
assert serialize_level(skew) == "1,#,2,#,3,#,#"
assert serialize_pre(None) == "#" and deserialize_pre("#") is None
assert build_pre_in([], []) is None
print("serialization and construction checks passed")
import java.util.*;
public class SerializeBuild {
static final class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
static TreeNode build(Integer[] level) {
if (level.length == 0 || level[0] == null) return null;
TreeNode root = new TreeNode(level[0]);
ArrayDeque<TreeNode> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < level.length) {
TreeNode node = q.poll();
if (i < level.length && level[i] != null) { node.left = new TreeNode(level[i]); q.add(node.left); }
i++;
if (i < level.length && level[i] != null) { node.right = new TreeNode(level[i]); q.add(node.right); }
i++;
}
return root;
}
static String serializePre(TreeNode root) {
StringJoiner sj = new StringJoiner(",");
serializePre(root, sj);
return sj.toString();
}
private static void serializePre(TreeNode n, StringJoiner sj) {
if (n == null) { sj.add("#"); return; }
sj.add(Integer.toString(n.val));
serializePre(n.left, sj);
serializePre(n.right, sj);
}
static TreeNode deserializePre(String data) {
return deserializePre(data.split(","), new int[]{0});
}
private static TreeNode deserializePre(String[] tok, int[] at) {
String t = tok[at[0]++];
if (t.equals("#")) return null;
TreeNode n = new TreeNode(Integer.parseInt(t));
n.left = deserializePre(tok, at);
n.right = deserializePre(tok, at);
return n;
}
static String serializeLevel(TreeNode root) {
StringJoiner sj = new StringJoiner(",");
ArrayDeque<Optional<TreeNode>> q = new ArrayDeque<>(); // ArrayDeque rejects null, so wrap
q.add(Optional.ofNullable(root));
while (!q.isEmpty()) {
Optional<TreeNode> o = q.poll();
if (o.isEmpty()) { sj.add("#"); continue; }
TreeNode n = o.get();
sj.add(Integer.toString(n.val));
q.add(Optional.ofNullable(n.left));
q.add(Optional.ofNullable(n.right));
}
return sj.toString();
}
static TreeNode deserializeLevel(String data) {
String[] tok = data.split(",");
Integer[] level = new Integer[tok.length];
for (int i = 0; i < tok.length; i++) level[i] = tok[i].equals("#") ? null : Integer.valueOf(tok[i]);
return build(level);
}
static TreeNode buildPreIn(int[] pre, int[] in) {
Map<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < in.length; i++) pos.put(in[i], i);
return buildPreIn(pre, pos, new int[]{0}, 0, in.length - 1);
}
private static TreeNode buildPreIn(int[] pre, Map<Integer, Integer> pos, int[] idx, int lo, int hi) {
if (lo > hi) return null;
TreeNode n = new TreeNode(pre[idx[0]++]);
int m = pos.get(n.val);
n.left = buildPreIn(pre, pos, idx, lo, m - 1);
n.right = buildPreIn(pre, pos, idx, m + 1, hi);
return n;
}
static TreeNode buildPostIn(int[] post, int[] in) {
Map<Integer, Integer> pos = new HashMap<>();
for (int i = 0; i < in.length; i++) pos.put(in[i], i);
return buildPostIn(post, pos, new int[]{post.length - 1}, 0, in.length - 1);
}
private static TreeNode buildPostIn(int[] post, Map<Integer, Integer> pos, int[] idx, int lo, int hi) {
if (lo > hi) return null;
TreeNode n = new TreeNode(post[idx[0]--]);
int m = pos.get(n.val);
n.right = buildPostIn(post, pos, idx, m + 1, hi); // right first
n.left = buildPostIn(post, pos, idx, lo, m - 1);
return n;
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) {
TreeNode t = build(new Integer[]{1, 2, 3, 4, 5, null, 6, null, null, 7, 8});
String s = serializePre(t);
check(s.equals("1,2,4,#,#,5,7,#,#,8,#,#,3,#,6,#,#"), "preorder serialization");
check(serializePre(deserializePre(s)).equals(s), "preorder round trip");
String lv = serializeLevel(t);
check(lv.equals("1,2,3,4,5,#,6,#,#,7,8,#,#,#,#,#,#"), "level serialization");
check(serializePre(deserializeLevel(lv)).equals(s), "level round trip");
int[] pre = {1, 2, 4, 5, 7, 8, 3, 6}, in = {4, 2, 7, 5, 8, 1, 3, 6}, post = {4, 7, 8, 5, 2, 6, 3, 1};
check(serializePre(buildPreIn(pre, in)).equals(s), "pre+in");
check(serializePre(buildPostIn(post, in)).equals(s), "post+in");
TreeNode skew = build(new Integer[]{1, null, 2, null, 3});
check(serializePre(skew).equals("1,#,2,#,3,#,#") && serializeLevel(skew).equals("1,#,2,#,3,#,#"), "skewed");
check(serializePre(null).equals("#") && deserializePre("#") == null, "empty");
check(buildPreIn(new int[]{}, new int[]{}) == null, "empty build");
System.out.println("serialization and construction checks passed");
}
}
#include <cassert>
#include <deque>
#include <iostream>
#include <optional>
#include <queue>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
struct TreeNode {
int val;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
explicit TreeNode(int v) : val(v) {}
};
std::deque<TreeNode> arena;
TreeNode* make(int v) { arena.emplace_back(v); return &arena.back(); }
TreeNode* build(const std::vector<std::optional<int>>& level) {
if (level.empty() || !level[0]) return nullptr;
TreeNode* root = make(*level[0]);
std::queue<TreeNode*> q;
q.push(root);
size_t i = 1;
while (!q.empty() && i < level.size()) {
TreeNode* node = q.front(); q.pop();
if (i < level.size() && level[i]) { node->left = make(*level[i]); q.push(node->left); }
++i;
if (i < level.size() && level[i]) { node->right = make(*level[i]); q.push(node->right); }
++i;
}
return root;
}
std::vector<std::string> split(const std::string& s) {
std::vector<std::string> out;
std::stringstream ss(s);
std::string tok;
while (std::getline(ss, tok, ',')) out.push_back(tok);
return out;
}
std::string join(const std::vector<std::string>& parts) {
std::string s;
for (size_t i = 0; i < parts.size(); ++i) { if (i) s += ','; s += parts[i]; }
return s;
}
void serPre(TreeNode* n, std::vector<std::string>& out) {
if (!n) { out.push_back("#"); return; }
out.push_back(std::to_string(n->val));
serPre(n->left, out);
serPre(n->right, out);
}
std::string serializePre(TreeNode* root) { std::vector<std::string> out; serPre(root, out); return join(out); }
TreeNode* desPre(const std::vector<std::string>& tok, size_t& at) {
const std::string& t = tok[at++];
if (t == "#") return nullptr;
TreeNode* n = make(std::stoi(t));
n->left = desPre(tok, at);
n->right = desPre(tok, at);
return n;
}
TreeNode* deserializePre(const std::string& data) { auto tok = split(data); size_t at = 0; return desPre(tok, at); }
std::string serializeLevel(TreeNode* root) {
std::vector<std::string> out;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* n = q.front(); q.pop();
if (!n) { out.push_back("#"); continue; }
out.push_back(std::to_string(n->val));
q.push(n->left);
q.push(n->right);
}
return join(out);
}
TreeNode* deserializeLevel(const std::string& data) {
std::vector<std::optional<int>> level;
for (const auto& t : split(data)) level.push_back(t == "#" ? std::nullopt : std::optional<int>(std::stoi(t)));
return build(level);
}
TreeNode* preIn(const std::vector<int>& pre, std::unordered_map<int, int>& pos, size_t& idx, int lo, int hi) {
if (lo > hi) return nullptr;
TreeNode* n = make(pre[idx++]);
int m = pos[n->val];
n->left = preIn(pre, pos, idx, lo, m - 1);
n->right = preIn(pre, pos, idx, m + 1, hi);
return n;
}
TreeNode* buildPreIn(const std::vector<int>& pre, const std::vector<int>& in) {
std::unordered_map<int, int> pos;
for (int i = 0; i < (int)in.size(); ++i) pos[in[i]] = i;
size_t idx = 0;
return preIn(pre, pos, idx, 0, (int)in.size() - 1);
}
TreeNode* postIn(const std::vector<int>& post, std::unordered_map<int, int>& pos, int& idx, int lo, int hi) {
if (lo > hi) return nullptr;
TreeNode* n = make(post[idx--]);
int m = pos[n->val];
n->right = postIn(post, pos, idx, m + 1, hi); // right first
n->left = postIn(post, pos, idx, lo, m - 1);
return n;
}
TreeNode* buildPostIn(const std::vector<int>& post, const std::vector<int>& in) {
std::unordered_map<int, int> pos;
for (int i = 0; i < (int)in.size(); ++i) pos[in[i]] = i;
int idx = (int)post.size() - 1;
return postIn(post, pos, idx, 0, (int)in.size() - 1);
}
int main() {
using std::nullopt;
TreeNode* t = build({1, 2, 3, 4, 5, nullopt, 6, nullopt, nullopt, 7, 8});
std::string s = serializePre(t);
assert(s == "1,2,4,#,#,5,7,#,#,8,#,#,3,#,6,#,#");
assert(serializePre(deserializePre(s)) == s);
std::string lv = serializeLevel(t);
assert(lv == "1,2,3,4,5,#,6,#,#,7,8,#,#,#,#,#,#");
assert(serializePre(deserializeLevel(lv)) == s);
std::vector<int> pre{1, 2, 4, 5, 7, 8, 3, 6}, in{4, 2, 7, 5, 8, 1, 3, 6}, post{4, 7, 8, 5, 2, 6, 3, 1};
assert(serializePre(buildPreIn(pre, in)) == s);
assert(serializePre(buildPostIn(post, in)) == s);
TreeNode* skew = build({1, nullopt, 2, nullopt, 3});
assert(serializePre(skew) == "1,#,2,#,3,#,#" && serializeLevel(skew) == "1,#,2,#,3,#,#");
assert(serializePre(nullptr) == "#" && deserializePre("#") == nullptr);
assert(buildPreIn({}, {}) == nullptr);
std::cout << "serialization and construction checks passed\n";
}
class TreeNode {
val: number;
left: TreeNode | null = null;
right: TreeNode | null = null;
constructor(val: number) {
this.val = val;
}
}
function build(level: (number | null)[]): TreeNode | null {
if (level.length === 0 || level[0] === null) return null;
const root = new TreeNode(level[0]);
const q: TreeNode[] = [root];
let head = 0;
let i = 1;
while (head < q.length && i < level.length) {
const node = q[head++];
const l = level[i++];
if (l !== null && l !== undefined) { node.left = new TreeNode(l); q.push(node.left); }
const r = i < level.length ? level[i] : null;
i++;
if (r !== null && r !== undefined) { node.right = new TreeNode(r); q.push(node.right); }
}
return root;
}
function serializePre(root: TreeNode | null): string {
const out: string[] = [];
const go = (n: TreeNode | null): void => {
if (!n) { out.push("#"); return; }
out.push(String(n.val));
go(n.left);
go(n.right);
};
go(root);
return out.join(",");
}
function deserializePre(data: string): TreeNode | null {
const tok = data.split(",");
let at = 0;
const go = (): TreeNode | null => {
const t = tok[at++];
if (t === "#") return null;
const n = new TreeNode(Number(t));
n.left = go();
n.right = go();
return n;
};
return go();
}
function serializeLevel(root: TreeNode | null): string {
const out: string[] = [];
const q: (TreeNode | null)[] = [root];
for (let head = 0; head < q.length; head++) {
const n = q[head];
if (!n) { out.push("#"); continue; }
out.push(String(n.val));
q.push(n.left, n.right);
}
return out.join(",");
}
function deserializeLevel(data: string): TreeNode | null {
return build(data.split(",").map((t) => (t === "#" ? null : Number(t))));
}
function buildPreIn(pre: number[], ino: number[]): TreeNode | null {
const pos = new Map<number, number>();
ino.forEach((v, i) => pos.set(v, i));
let idx = 0;
const go = (lo: number, hi: number): TreeNode | null => {
if (lo > hi) return null;
const n = new TreeNode(pre[idx++]);
const m = pos.get(n.val)!;
n.left = go(lo, m - 1);
n.right = go(m + 1, hi);
return n;
};
return go(0, ino.length - 1);
}
function buildPostIn(post: number[], ino: number[]): TreeNode | null {
const pos = new Map<number, number>();
ino.forEach((v, i) => pos.set(v, i));
let idx = post.length - 1;
const go = (lo: number, hi: number): TreeNode | null => {
if (lo > hi) return null;
const n = new TreeNode(post[idx--]);
const m = pos.get(n.val)!;
n.right = go(m + 1, hi); // right first
n.left = go(lo, m - 1);
return n;
};
return go(0, ino.length - 1);
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error(what);
}
const t = build([1, 2, 3, 4, 5, null, 6, null, null, 7, 8]);
const s = serializePre(t);
check(s === "1,2,4,#,#,5,7,#,#,8,#,#,3,#,6,#,#", "preorder serialization");
check(serializePre(deserializePre(s)) === s, "preorder round trip");
const lv = serializeLevel(t);
check(lv === "1,2,3,4,5,#,6,#,#,7,8,#,#,#,#,#,#", "level serialization");
check(serializePre(deserializeLevel(lv)) === s, "level round trip");
const pre = [1, 2, 4, 5, 7, 8, 3, 6], ino = [4, 2, 7, 5, 8, 1, 3, 6], post = [4, 7, 8, 5, 2, 6, 3, 1];
check(serializePre(buildPreIn(pre, ino)) === s, "pre+in");
check(serializePre(buildPostIn(post, ino)) === s, "post+in");
const skew = build([1, null, 2, null, 3]);
check(serializePre(skew) === "1,#,2,#,3,#,#" && serializeLevel(skew) === "1,#,2,#,3,#,#", "skewed");
check(serializePre(null) === "#" && deserializePre("#") === null, "empty");
check(buildPreIn([], []) === null, "empty build");
console.log("serialization and construction checks passed");
Variant: construction without a hash map
The stop-value construction consumes preorder and inorder with one index each. go(stop) builds the subtree that ends just before inorder reaches stop: if the next inorder value is stop, the subtree is empty; otherwise the next preorder value is its root, its left subtree ends at the root's value, and its right subtree ends at the same stop as the parent's.
def build_pre_in_no_map(pre: list[int], ino: list[int]):
class Node:
def __init__(self, v): self.val, self.left, self.right = v, None, None
p = i = 0
SENTINEL = object()
def go(stop):
nonlocal p, i
if i < len(ino) and ino[i] is not stop and (stop is SENTINEL or ino[i] != stop):
node = Node(pre[p]); p += 1
node.left = go(node.val) # left subtree ends where inorder reaches node
i += 1 # consume node itself from inorder
node.right = go(stop) # right subtree ends where the parent's does
return node
return None
return go(SENTINEL)
def pre_of(n): return [] if n is None else [n.val] + pre_of(n.left) + pre_of(n.right)
def in_of(n): return [] if n is None else in_of(n.left) + [n.val] + in_of(n.right)
P, I = [1, 2, 4, 5, 7, 8, 3, 6], [4, 2, 7, 5, 8, 1, 3, 6]
r = build_pre_in_no_map(P, I)
assert pre_of(r) == P and in_of(r) == I
assert build_pre_in_no_map([], []) is None
Every node is created once and every inorder element is consumed once, so it is time with only the recursion stack as extra space.
Real-world uses
The DOM and the browser. The DOM specification defines tree order as preorder, depth-first. document.querySelectorAll returns matches in tree order, TreeWalker and NodeIterator walk it, and Node.compareDocumentPosition answers "which comes first in preorder?". The DOM's firstChild / nextSibling pointers are the left-child right-sibling representation. Layout engines then do a postorder pass (sizes of children before the parent) and a preorder pass (positions from parent to children); the next lesson develops that pair.
Compilers and interpreters. A parser produces an abstract syntax tree; type checking, constant folding and code generation for expressions are postorder walks, because an operator's operands must be processed first. Emitting a postorder walk of an expression tree is generating stack-machine bytecode (push a, push b, add), which is why Stacks and this lesson meet at shunting-yard. CPython's ast.walk documents its order as unspecified (the implementation happens to be breadth-first with a deque), and ast.NodeVisitor is a recursive preorder dispatcher.
File systems and shell tools. du must know each subdirectory's size before its parent's — postorder. rm -r must delete a directory's contents before the directory — postorder. find prints in preorder by default and switches to postorder with -depth, precisely so that find … -depth -delete removes children first. tree and ls -R are preorder.
Serialization formats. JSON, XML, protobuf and S-expressions write a tree in preorder with explicit structure markers (brackets, lengths, end tags). Their recursive-descent parsers are this page's deserializer, and production parsers cap nesting depth so deep input cannot overflow the call stack.
Databases and ordered indexes. A B+-tree range scan is an inorder traversal restricted to a key interval, with leaves chained so the scan becomes a list walk (Database Indexing Deep Dive, Storage Engines). std::map and Java's TreeMap iterate with the parent-pointer successor walk from the ladder; heaps use the array layout.
Garbage collectors. Marking is a depth-first traversal of the object graph, done with an explicit mark stack. The Schorr–Waite algorithm marks with no stack by temporarily reversing pointers — the same borrow-and-restore idea as Morris (Memory Allocators).
Pitfalls & edge cases
- Empty tree. Return an empty result for
root = null, and never push null into a stack that rejects it (Java'sArrayDeque.push(null)throws). - Recursion depth on skewed trees. Sorted insertions into a plain BST make a path; recursion over 100,000 nodes fails in CPython and usually in Java. Raising
sys.setrecursionlimitjust moves the crash into the interpreter's C stack. - Height conventions. Edges versus nodes shifts every formula by one; LeetCode's "maximum depth" counts nodes.
- Level-order formats. Indexing a LeetCode array with builds the wrong tree as soon as a null appears, because children of nulls are not written.
- Level-size snapshot. Read the queue length once per level, not in the loop condition.
- Postorder
prevcheck. Compare node references, not values, or duplicates break it. - Morris left half-done. Returning early leaves threads, so the tree has a cycle and the next traversal loops forever.
- Serialization. Use a separator for multi-digit and negative values, escape values equal to the marker, and serialize the empty tree as
"#", not as the empty string. - Construction with duplicates. The hash map keeps one index per value and silently builds a wrong tree.
- Vertical-order ties. The 314 and 987 rules differ only on same-row, same-column collisions, so small tests pass and hidden ones fail.
- Catalan overflow. fits in a signed 32-bit integer and does not. 64-bit integers hold up to .
Variations
- -ary trees. Preorder, postorder and level order generalise directly; inorder has no canonical meaning beyond two children.
- Threaded binary trees. Permanent threads with a flag bit per pointer: stackless iteration without mutation, paid for on every insert and delete.
- Euler tour. Entry and exit times turn "is an ancestor of ?" into interval containment and subtree queries into array range queries (LCA, Binary Lifting & Euler Tour).
- Boundary traversal. Left boundary, leaves, reversed right boundary; the trap is double-counting corners.
- Generators. Python's
yield fromor C# iterators let you write the recursive traversal and consume it lazily; depth limits still apply.
Practice ladder
Each problem is described in my own words. Solutions are Python and run as part of this page's checks.
- Binary Tree Inorder Traversal (LeetCode 94) — Easy. Return the inorder sequence. Teaches the go-left loop; do it iteratively and then with Morris.
Hint
Push while going left; pop, emit, go right. For Morris, thread the predecessor's right pointer to cur on first arrival.
- Binary Tree Preorder Traversal (LeetCode 144) — Easy. Return the preorder. Teaches push-right-then-left.
Hint
One stack; pop, emit, push right child first so the left child is popped next.
- Binary Tree Postorder Traversal (LeetCode 145) — Easy. Return the postorder without recursion. Teaches the
prevtest or the reversed node-right-left preorder.
Hint
Either reverse a "node, right, left" preorder, or peek at the stack top and go right only if its right child is not the node you emitted last.
- Binary Tree Level Order Traversal (LeetCode 102) — Medium. Group nodes by depth. Teaches the level-size snapshot.
Hint
Read the queue length once at the start of each level and process exactly that many nodes.
- Binary Tree Zigzag Level Order Traversal (LeetCode 103) — Medium. Levels with alternating direction. Teaches that direction is a property of the output, not of the traversal.
Hint
Do a plain level-order BFS and reverse the odd levels, or fill each level's list from the back when the level index is odd.
- Check Completeness of a Binary Tree (LeetCode 958) — Medium. Decide whether a tree is complete. Teaches the BFS characterisation of completeness.
Hint
BFS including null children. A tree is complete iff no real node appears after the first null.
Solution
from collections import deque
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def is_complete(root) -> bool:
q, seen_null = deque([root]), False
while q:
n = q.popleft()
if n is None:
seen_null = True
else:
if seen_null:
return False # a real node after a gap
q.append(n.left); q.append(n.right)
return True
assert is_complete(Node(1, Node(2, Node(4), Node(5)), Node(3, Node(6))))
assert not is_complete(Node(1, Node(2, None, Node(5)), Node(3)))
assert is_complete(None)
time, space. Correct because level order with nulls lists the slots of a complete tree as a run of real nodes followed by a run of nulls, and any other shape puts a null before some real node.
- Verify Preorder Serialization of a Binary Tree (LeetCode 331) — Medium. Validate a preorder string with
#markers without building the tree. Teaches the open-slot counting lemma from the Correctness section.
Hint
Start with one open slot. Every token fills one; every value opens two. Fail if you need a slot when none is open; succeed iff exactly zero remain at the end.
Solution
def is_valid_serialization(preorder: str) -> bool:
slots = 1
for tok in preorder.split(","):
if slots == 0:
return False # tokens after the tree was complete
slots -= 1
if tok != "#":
slots += 2
return slots == 0
assert is_valid_serialization("1,2,4,#,#,5,7,#,#,8,#,#,3,#,6,#,#")
assert not is_valid_serialization("1,#")
assert not is_valid_serialization("#,1")
assert is_valid_serialization("#")
time, space beyond the split. The counter is "markers still needed minus markers seen", and the lemma says a valid encoding hits zero exactly at its last token.
- Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105) — Medium. Rebuild the tree. Teaches the root-and-split recursion and the hash-map speedup.
Hint
One moving index into preorder, a map from value to inorder position, and (lo, hi) bounds on the inorder range.
- Construct Binary Tree from Inorder and Postorder Traversal (LeetCode 106) — Medium. Same, from the other side. Teaches why the right subtree is built first.
Hint
Read postorder from the end: root, then the right subtree's nodes, then the left's.
- Construct Binary Tree from Preorder and Postorder Traversal (LeetCode 889) — Medium. Return any tree matching both. Teaches the ambiguity and the full-tree recursion.
Hint
`pre[1]` is the left child's root (if a left child exists — choose to make the single child left). Its position in postorder gives the left subtree's size.
Solution
```python
class Node:
def __init__(self, v): self.val, self.left, self.right = v, None, None
def construct_from_pre_post(pre: list[int], post: list[int]):
pos = {v: i for i, v in enumerate(post)}
def go(a: int, b: int, c: int) -> "Node | None":
# pre[a..b] and post[c..c + (b - a)] describe the same subtree
if a > b:
return None
node = Node(pre[a])
if a == b:
return node
left_size = pos[pre[a + 1]] - c + 1 # left child's root ends its postorder block
node.left = go(a + 1, a + left_size, c)
node.right = go(a + left_size + 1, b, c + left_size)
return node
return go(0, len(pre) - 1, 0)
def pre_of(n): return [] if n is None else [n.val] + pre_of(n.left) + pre_of(n.right)
def post_of(n): return [] if n is None else post_of(n.left) + post_of(n.right) + [n.val]
P, Q = [1, 2, 4, 5, 3, 6, 7], [4, 5, 2, 6, 7, 3, 1]
r = construct_from_pre_post(P, Q)
assert pre_of(r) == P and post_of(r) == Q
r2 = construct_from_pre_post([1, 2], [2, 1]) # ambiguous: we choose a left child
assert r2.left.val == 2 and r2.right is None
```
<span class="math" data-tex="O(n)"></span> time with the position map. When a node has a single child this puts it on the left, which is one of the <span class="math" data-tex="2^s"></span> valid answers.
- Serialize and Deserialize Binary Tree (LeetCode 297) — Hard. Design both directions. Teaches preorder or level order with markers, and the uniqueness proof.
Hint
Preorder with `#` for null and a recursive decoder reading from a token iterator; or level order with a queue on both sides if depth is a concern.
- Vertical Order Traversal of a Binary Tree (LeetCode 987) — Hard. Columns left to right; within a column by row, ties by value. Teaches carrying coordinates through a traversal and stating tie rules.
Hint
Collect `(col, row, val)` for every node with any traversal, sort the triples, group by column.
- Maximum Width of Binary Tree (LeetCode 662) — Medium. Widest level, counting the gaps between end nodes. Teaches heap-layout indices on an arbitrary tree.
Hint
Give the root index 0 and children <span class="math" data-tex="2i + 1"></span>, <span class="math" data-tex="2i + 2"></span>; the width of a level is last index minus first index plus one. Re-base indices per level so they do not grow to <span class="math" data-tex="2^{3000}"></span> (Python is fine either way; fixed-width integers are not).
Solution
```python
from collections import deque
class Node:
def __init__(self, v, l=None, r=None): self.val, self.left, self.right = v, l, r
def width_of_binary_tree(root) -> int:
best, q = 0, deque([(root, 0)] if root else [])
while q:
base = q[0][1]
first = last = 0
for _ in range(len(q)):
node, i = q.popleft()
i -= base # re-base so indices stay small
last = i
if node.left: q.append((node.left, 2 * i + 1))
if node.right: q.append((node.right, 2 * i + 2))
best = max(best, last - first + 1)
return best
t = Node(1, Node(3, Node(5), Node(3)), Node(2, None, Node(9)))
assert width_of_binary_tree(t) == 4 # level 2 spans slots 0..3
assert width_of_binary_tree(Node(1)) == 1
assert width_of_binary_tree(None) == 0
```
<span class="math" data-tex="O(n)"></span> time, <span class="math" data-tex="O(w)"></span> space.
- Unique Binary Search Trees (LeetCode 96) — Medium. Count BSTs on keys . Teaches the Catalan recurrence (and its sibling LeetCode 95, which generates them all).
Hint
Choose the root <span class="math" data-tex="k"></span>; the left subtree is any BST on <span class="math" data-tex="k - 1"></span> keys and the right any BST on <span class="math" data-tex="n - k"></span> keys.
- Recover Binary Search Tree (LeetCode 99) — Medium. Two nodes of a BST were swapped; fix it. The follow-up asks for space. Teaches Morris inorder as a tool, not a curiosity.
Hint
An inorder scan of a BST is sorted. A swap creates one or two "descents" (`prev.val > cur.val`). The first swapped node is `prev` at the first descent; the second is `cur` at the last descent. Run the scan with Morris for <span class="math" data-tex="O(1)"></span> space.
Common mistakes & interview follow-ups
"Now do it without recursion." Go-left loop for inorder; the visited-flag template for any order.
"What if the tree is a million nodes in a line?" Explicit stack, or Morris if memory is tight.
"Make it an iterator in O(h) memory." Constructor pushes the left spine; next() pops, then pushes the left spine of the popped node's right child. Amortized (LeetCode 173).
"Can you do it in O(1) space?" Morris; be ready to argue restoration and the edge-disjoint spines bound.
"Serialize it more compactly." For a BST with distinct keys, preorder alone suffices (inorder is the sorted order). For a complete tree, level order without markers. In general, two bits per node ("has left", "has right") in preorder — near the bits needed for the shape.
"What if values repeat?" Construction from two traversals breaks; serialization with markers still works.
Common mistakes seen in interviews: pushing the left child before the right in iterative preorder; forgetting cur = cur.right after popping in inorder; using 2i + 1 indexing on a LeetCode level-order array; returning early out of Morris; slicing arrays in the construction recursion and calling it .
Quick quiz
- A binary tree has 1,000 nodes. How many null child pointers does it have, and what is the minimum possible height?
Answer
1,001 null pointers (). Minimum height is , achieved by a complete tree (a perfect tree of height 9 holds 1,023 nodes).
- Preorder is
3, 9, 20, 15, 7and inorder is9, 3, 15, 20, 7. What is the postorder?
Answer
Root 3; inorder splits into left {9} and right {15, 20, 7}. Right subtree: preorder 20, 15, 7, inorder 15, 20, 7, so root 20 with children 15 and 7. Postorder: 9, 15, 7, 20, 3.
- Why does the inner
whileloop in Morris traversal not make the algorithm on a tree where every node has a long left subtree?
Answer
Each inner loop walks the right spine of one node's left subtree, twice. Every right edge belongs to the spine of at most one such node, so all spines together contain at most edges and the inner loops total at most steps over the whole run.
- Which of these determine a binary tree with distinct values uniquely: (a) preorder with null markers, (b) inorder with null markers, (c) preorder + postorder, (d) level order with null markers?
Answer
(a) and (d). (b) is just the inorder sequence interleaved with markers, the same for every tree with that inorder. (c) is ambiguous whenever some node has exactly one child.
- How many structurally different binary trees have 5 nodes, and how many BSTs hold the keys 1 to 5?
Answer
Both are .
Further reading / sources
- Knuth, The Art of Computer Programming, Vol. 1, 3rd ed., §2.3.1 "Traversing Binary Trees" (including threaded trees and the stackless traversal discussion) and §2.3.4.4 on enumeration of trees (Catalan numbers).
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., §10.3 "Representing rooted trees" and Chapter 12 "Binary Search Trees" (§12.1 inorder walk; exercises 12.1-3 on stackless traversal).
- Sedgewick & Wayne, Algorithms, 4th ed., §3.2 "Binary Search Trees" (traversal and ordered iteration).
- J. M. Morris, "Traversing binary trees simply and cheaply", Information Processing Letters 9(5), 1979, pp. 197–200.
- A. J. Perlis & C. Thornton, "Symbol manipulation by threaded lists", Communications of the ACM 3(4), 1960.
- H. Schorr & W. M. Waite, "An efficient machine-independent procedure for garbage collection in various list structures", Communications of the ACM 10(8), 1967 — pointer reversal marking.
- B. Reed, "The height of a random binary search tree", Journal of the ACM 50(3), 2003.
- WHATWG DOM Standard — definition of tree order.
- Wikipedia: Tree traversal and Catalan number.
Prev: Trees (Overview) · Next: Tree Problem Patterns
Related: Module 3 · Trees · Recursion & Mathematical Induction · Stacks · Queues, Deques & Circular Buffers · Binary Search Trees · Heaps & Priority Queues · LCA, Binary Lifting & Euler Tour · Graphs · DSA: Zero to Mastery