Binary Tree Fundamentals
Core Idea: Trees are recursive structures - every subtree is itself a tree. Most solutions exploit this by solving for subtrees and combining results.
Two Traversal Paradigms:
- DFS (Depth-First): Go deep before wide. Natural with recursion. Use when answer depends on subtree properties.
- BFS (Breadth-First): Go level by level. Use queue. Use when answer depends on level structure or shortest path.
The Recursive Template:
func solve(root *TreeNode) Result:
if root == nil:
return BASE_CASE
left := solve(root.Left)
right := solve(root.Right)
return COMBINE(root, left, right)
Key Insight:
Trust the Recursion: Assume solve(root.Left) correctly solves for the left subtree. Your job is only to combine left result, right result, and current node correctly.
Base Case Matters: nil nodes return identity values (0 for height, true for validation, etc.).
DFS vs BFS: When to Use Which?
Use DFS When:
- Need subtree properties (height, size, sum)
- Need to validate structural properties (balanced, BST)
- Path problems (root-to-leaf, any path)
- Need to modify tree structure (invert, delete)
Use BFS When:
- Need level-order traversal
- Need to process level by level (level averages, rightmost view)
- Finding minimum depth (first leaf encountered)
- Need nodes at same depth together
DFS Template (Recursive):
func dfs(root *TreeNode):
if root == nil: return
// Pre-order: process BEFORE children
dfs(root.Left)
// In-order: process BETWEEN children
dfs(root.Right)
// Post-order: process AFTER children
BFS Template (Iterative):
queue := []*TreeNode{root}
for len(queue) > 0:
levelSize := len(queue)
for i := 0; i < levelSize; i++:
node := queue[0]
queue = queue[1:]
// Process node
if node.Left != nil: queue = append(queue, node.Left)
if node.Right != nil: queue = append(queue, node.Right)
// Level complete - increment level counter, etc.
Level Tracking:
Capture len(queue) at start of each level to know when level ends.
Invert Binary Tree
O(n) Time / O(h) Space
Goal: Mirror the tree - every left child becomes right and vice versa.
Technique: Post-Order DFS
Why Post-Order? We need inverted subtrees before swapping. Invert children first, then swap them at current node. (Pre-order also works here since order doesn't affect correctness.)
Key Insight: Trust recursion - invertTree(root.Left) returns a fully inverted left subtree. Just swap the two inverted subtrees.
func invertTree(root *TreeNode) *TreeNode:
if root == nil:
return nil
left := invertTree(root.Left) // inverted left subtree
right := invertTree(root.Right) // inverted right subtree
root.Left, root.Right = right, left // swap
return root
Foundation:
Simplest tree modification - practice trusting recursion here.
Maximum Depth of Binary Tree
O(n) Time / O(h) Space
Goal: Find the longest root-to-leaf path (number of nodes).
Technique 1: DFS (Recursive)
Why DFS? Depth depends on subtree depths. Get max depth of left and right, add 1 for current node.
func maxDepth(root *TreeNode) int:
if root == nil:
return 0
left := maxDepth(root.Left)
right := maxDepth(root.Right)
return 1 + max(left, right)
Technique 2: BFS (Level-Order)
Why BFS? Count levels directly. Each complete level iteration = 1 depth.
func maxDepthBFS(root *TreeNode) int:
if root == nil: return 0
queue := []*TreeNode{root}
depth := 0
for len(queue) > 0:
levelSize := len(queue)
for i := 0; i < levelSize; i++:
node := queue[0]
queue = queue[1:]
if node.Left != nil: queue = append(queue, node.Left)
if node.Right != nil: queue = append(queue, node.Right)
depth++
return depth
Base Case:
Empty tree has depth 0, not -1.
Diameter of Binary Tree
O(n) Time / O(h) Space
Goal: Find longest path between any two nodes (measured in edges).
Technique: DFS with Global State
Why Global State? We compute height (returned value) but track diameter (global). The longest path through a node = leftHeight + rightHeight. But the longest overall might not pass through root.
Key Insight: At each node, we have a candidate diameter (left + right heights). Update global max. Return height (not diameter) for parent's calculation.
func diameterOfBinaryTree(root *TreeNode) int:
maxDiameter := 0
var getHeight func(*TreeNode) int
getHeight = func(node *TreeNode) int:
if node == nil:
return 0
left := getHeight(node.Left)
right := getHeight(node.Right)
// Diameter through this node
maxDiameter = max(maxDiameter, left + right)
// Return height for parent
return 1 + max(left, right)
getHeight(root)
return maxDiameter
Two-Value Pattern:
Compute X (height), track Y (diameter). Return X, update Y globally.
Return vs Track:
Height is returned (parent needs it). Diameter is tracked (comparing candidates).
Balanced Binary Tree
O(n) Time / O(h) Space
Goal: Check if every node's left and right subtrees differ in height by at most 1.
Technique: DFS with Global Flag
Why Global Flag? Same pattern as diameter - compute height, track balance. Once we find an imbalanced node, set flag false.
Key Insight: At each node, check |leftHeight - rightHeight| <= 1. If violated anywhere, tree is unbalanced.
func isBalanced(root *TreeNode) bool:
balanced := true
var getHeight func(*TreeNode) int
getHeight = func(node *TreeNode) int:
if node == nil:
return 0
left := getHeight(node.Left)
right := getHeight(node.Right)
if abs(left - right) > 1:
balanced = false
return 1 + max(left, right)
getHeight(root)
return balanced
Alternative: Return -1 for Imbalanced
// Return -1 if subtree is imbalanced
var getHeight func(*TreeNode) int
getHeight = func(node *TreeNode) int:
if node == nil: return 0
left := getHeight(node.Left)
if left == -1: return -1 // early exit
right := getHeight(node.Right)
if right == -1: return -1
if abs(left-right) > 1: return -1
return 1 + max(left, right)
return getHeight(root) != -1
Early Exit:
Once imbalanced, propagate -1 up to skip unnecessary work.
Same Binary Tree
O(n) Time / O(h) Space
Goal: Check if two trees have identical structure and values.
Technique: Parallel DFS
Why Parallel? Compare corresponding nodes in both trees simultaneously. If any pair differs, trees are different.
Key Insight: Both nil = same. One nil = different. Values differ = different. Otherwise, check both children match.
func isSameTree(p, q *TreeNode) bool:
// Both nil - same (base case)
if p == nil && q == nil:
return true
// One nil or values differ - different
if p == nil || q == nil || p.Val != q.Val:
return false
// Both subtrees must match
return isSameTree(p.Left, q.Left) &&
isSameTree(p.Right, q.Right)
Short-Circuit:
AND (&&) stops at first false - efficient for mismatched trees.
Order Matters:
Check nil cases before accessing .Val to avoid nil pointer dereference.
Subtree of Another Tree
O(m*n) Time / O(h) Space
Goal: Check if subRoot is a subtree of root (exact structure and values match).
Technique: DFS + Same Tree Check
Why Two Functions? For each node in root, check "is subRoot the same as the subtree rooted here?" Use same-tree as a subroutine.
Key Insight: If same-tree check fails at current node, the subtree might still exist in left or right children. Keep searching.
func isSubtree(root, subRoot *TreeNode) bool:
// Helper: same tree check
var sameTree func(*TreeNode, *TreeNode) bool
sameTree = func(p, q *TreeNode) bool:
if p == nil && q == nil: return true
if p == nil || q == nil || p.Val != q.Val: return false
return sameTree(p.Left, q.Left) && sameTree(p.Right, q.Right)
// Main logic
if root == nil && subRoot == nil: return true
if root == nil || subRoot == nil: return false
// Check: is subRoot same as current subtree?
if sameTree(root, subRoot):
return true
// Otherwise, search in children
return isSubtree(root.Left, subRoot) ||
isSubtree(root.Right, subRoot)
Composition Pattern:
Complex problems often combine simpler subroutines.
Edge Case:
root=[1,1], subRoot=[1] - sameTree fails at root, but subtree exists in left child.
Subtree: O(m+n) via String Matching
The naive approach is O(m*n). We can do O(m+n) by serializing trees and using pattern matching:
Step 1: Serialize Trees
Convert trees to strings using preorder traversal. Use separators to prevent false matches:
func serialize(root *TreeNode) string:
if root == nil: return "$#"
return "$" + strconv.Itoa(root.Val) +
serialize(root.Left) + serialize(root.Right)
Tree [12] → "$12$#$#"
Tree [2] → "$2$#$#" // Not a substring!
Why "$" prefix?
Without it, "2##" is substring of "12##" but [2] is NOT subtree of [12].
Step 2: Pattern Matching
Check if serialized subRoot is a substring of serialized root using KMP or Z-function.
KMP (Knuth-Morris-Pratt)
O(n+m) Time / O(m) Space
Core Idea: When mismatch occurs, don't restart - use what we already matched.
LPS Array (Longest Proper Prefix = Suffix)
lps[i] = length of longest proper prefix of pattern[0..i] that's also a suffix.
Pattern: A B A B C
Index: 0 1 2 3 4
LPS: 0 0 1 2 0
LPS[3]=2: "ABAB" has prefix "AB" = suffix "AB"
Why LPS Helps:
Text: ...A B A B X...
Pattern: A B A B C
^ mismatch at j=4
We matched "ABAB". LPS[3]=2 tells us the last 2
chars ("AB") equal the first 2. Jump to j=2:
Text: ...A B A B X...
Pattern: A B A B C
^ continue from j=2
Build LPS:
func buildLPS(pattern string) []int:
lps := make([]int, len(pattern))
length := 0 // length of prev longest prefix-suffix
i := 1
for i < len(pattern):
if pattern[i] == pattern[length]:
length++
lps[i] = length
i++
else if length != 0:
length = lps[length-1] // try shorter
else:
lps[i] = 0
i++
return lps
KMP Search:
func kmpSearch(text, pattern string) bool:
lps := buildLPS(pattern)
i, j := 0, 0 // text index, pattern index
for i < len(text):
if text[i] == pattern[j]:
i++; j++
if j == len(pattern): return true
else if j != 0:
j = lps[j-1] // use LPS to skip
else:
i++
return false
Mental Model:
"When I fail at position j, where in pattern can I resume?"
Z-Function Algorithm
O(n+m) Time / O(n+m) Space
Core Idea: z[i] = length of longest substring starting at s[i] that matches a prefix of s.
Z-Array Example:
String: a a b x a a b
Index: 0 1 2 3 4 5 6
Z: - 1 0 0 3 1 0
z[1]=1: s[1..1]="a" matches prefix s[0..0]="a"
z[4]=3: s[4..6]="aab" matches prefix s[0..2]="aab"
Pattern Matching with Z:
1. Combine: pattern + "|" + text
2. Compute Z-array
3. If any z[i] == len(pattern) for i > len(pattern),
pattern exists in text!
Find "aab" in "xaabx":
Combined: "aab|xaabx"
Z: - 1 0 0 0 3 1 0 0
^ z[5]=3 = len("aab") ✓
Z-Box: The "Cloned Photograph" Model
Think of the Z-box [l,r] as a photograph of the start of the string that's been pasted further down.
What "Inside the Z-box" Means (i ≤ r):
If box is [l=10, r=15], indices 10-15 are an exact clone of indices 0-5. When i is between l and r, you're standing in that cloned area.
The Three Key Operations:
1. The Mirror (i - l): Since you're in a clone, look back at your "twin" position in the original prefix.
z[i] = z[i - l] // What did my twin see?
2. The Safety Limit (r - i + 1): Your twin might have matched way beyond what your "photograph" covers. You can only trust up to the edge of the box.
z[i] = min(r - i + 1, z[i - l])
↑ chars left ↑ twin's match
in photo
Example:
Twin says "I matched 100 chars" but you only have 3 chars left in your photo → you can only guarantee those 3.
3. The Explorer (while loop): After using memory to get a head start, check characters past the edge to extend the match.
Updating the Box (High Water Mark):
Why update? When the explorer finds matches past r, we have a new, further-reaching "photograph." Algorithm is greedy—always wants r as far right as possible.
Why update l = i? Re-centers your coordinate system. Distance from l equals distance from prefix start, enabling the mirror calculation.
i + z[i] - 1 = ending index of current match
If this > r, we've expanded our known territory:
l = i // New anchor
r = i + z[i] - 1 // New high water mark
Z-Function Implementation
func zFunction(s string) []int:
n := len(s)
z := make([]int, n)
l, r := 0, 0 // [l,r] = rightmost match interval
for i := 1; i < n; i++:
if i <= r:
// INSIDE box: use mirror + safety limit
z[i] = min(r-i+1, z[i-l])
// EXPLORE: extend past the box edge
for i+z[i] < n && s[z[i]] == s[i+z[i]]:
z[i]++
// UPDATE: move high water mark if extended
if i+z[i]-1 > r:
l, r = i, i+z[i]-1
return z
Golden Rules:
- i - l = "Look at the original" (mirror position)
- r - i + 1 = "Don't trust beyond the photo edge" (safety limit)
- while loop = "Explore new territory"
- l, r update = "Relocate base to new high water mark"
Key Insight:
Text pointer never goes back. Work from discovering r is stored in Z-array and reused via the l anchor.
KMP vs Z-Function
Both achieve O(n+m) time. Mental model difference:
Strategic Approach:
KMP: "Reactive" - I failed at pattern position j.
Where can I restart without re-reading text?
Z-Alg: "Proactive" - I found a match here. Let me
map it so I skip work for upcoming chars.
KMP:
- Preprocess pattern only (O(m) space)
- Two-phase: build LPS, then search
- Better for streaming (process text char by char)
Z-Function:
- Process combined string (O(n+m) space)
- Single pass - preprocessing IS the search
- More intuitive: z[i] directly answers "prefix match length"
Subtree Application:
// Both work the same way:
serializedRoot := serialize(root)
serializedSub := serialize(subRoot)
// KMP: search directly
return kmpSearch(serializedRoot, serializedSub)
// Z-Function: combine then check
combined := serializedSub + "|" + serializedRoot
z := zFunction(combined)
// Check if any z[i] == len(serializedSub)
When to Use:
KMP for streaming/memory constraints. Z for simplicity.
Construct Tree from Preorder & Inorder
O(n) Time / O(n) Space
Goal: Given preorder and inorder traversals (unique values), rebuild the original binary tree.
What Each Traversal Tells You:
Preorder: root → left → right
→ First element is ALWAYS the root.
→ After the root, left subtree nodes come
first, then right subtree nodes.
Inorder: left → root → right
→ Everything LEFT of the root = left subtree.
→ Everything RIGHT of the root = right subtree.
→ Tells you the SIZE of each subtree.
The Key Insight:
Preorder identifies the root. Inorder splits left vs right. The left subtree's size bridges the two arrays.
Worked Example:
8
/ \
4 10 preorder = [8, 4, 2, 6, 10, 12]
/ \ \ inorder = [2, 4, 6, 8, 10, 12]
2 6 12
Step 1: root = 8 (first in preorder)
Step 2: Find 8 in inorder at index 3
left inorder: [2, 4, 6] (leftSize = 3)
right inorder: [10, 12]
Step 3: Use leftSize to split preorder
left preorder: [4, 2, 6] (next 3 after root)
right preorder: [10, 12] (the rest)
Step 4: Recurse on both halves
Recursive Decomposition:
preorder = [root | left subtree | right subtree]
inorder = [left subtree | root | right subtree]
↑
leftSize = index of root in inorder
left preorder = preorder[1 : leftSize+1]
left inorder = inorder[0 : leftSize]
right preorder = preorder[leftSize+1 :]
right inorder = inorder[leftSize+1 :]
Code:
func buildTree(preorder, inorder []int) *TreeNode:
if len(preorder) == 0:
return nil
root := &TreeNode{Val: preorder[0]}
leftSize := 0
for i, v := range inorder:
if v == root.Val:
leftSize = i
break
root.Left = buildTree(
preorder[1:leftSize+1], inorder[:leftSize])
root.Right = buildTree(
preorder[leftSize+1:], inorder[leftSize+1:])
return root
Optimisation:
Build a hashmap of inorder value→index upfront to make root lookup O(1) instead of O(n), reducing overall time from O(n²) to O(n).
Slice Sizes Must Match:
left preorder and left inorder must have the same length (leftSize). If they don't, the split is wrong.
Binary Tree Maximum Path Sum
O(n) Time / O(h) Space
Goal: Find the maximum sum of any non-empty path in the tree. A path connects adjacent nodes and cannot branch (no Y-shapes).
Technique: DFS with Global State (Diameter Pattern)
Why This Pattern? Same idea as diameter: at each node, compute two different things.
The Two Quantities:
1. COMPLETE PATH (updates global res):
Can use both children: left + node + right
"What if the best path passes through this node?"
2. EXTENDABLE CHAIN (returned to parent):
Can only use one child: node + max(left, right)
"What is the best single chain I can hand upward?"
Why different? If you returned both sides to your
parent, the parent would create a Y-shape = invalid.
Handling Negatives:
Clip child contributions to 0: If a child's best chain is negative, don't take that side. But never skip the node itself (all-negative trees must still return something).
left := max(dfs(node.Left), 0) // ignore if negative
right := max(dfs(node.Right), 0) // ignore if negative
complete path candidate = node.Val + left + right
extendable chain = node.Val + max(left, right)
Worked Example:
-15
/ \
10 20
/ \
15 5
/
-5
At node 15: left=-5→0, right=0→0
complete = 15, extendable = 15
At node 5: no children
complete = 5, extendable = 5
At node 20: left=15, right=5
complete = 15+20+5 = 40 ← global best!
extendable = 20+15 = 35 (pick better side)
At node -15: left=10, right=35
complete = 10+(-15)+35 = 30 (< 40)
extendable = -15+35 = 20
Answer: 40 (path 15→20→5, never goes through root)
Code:
func maxPathSum(root *TreeNode) int:
res := math.MinInt32
var dfs func(*TreeNode) int
dfs = func(node *TreeNode) int:
if node == nil:
return 0
left := max(dfs(node.Left), 0)
right := max(dfs(node.Right), 0)
// Complete path through this node
res = max(res, node.Val + left + right)
// Extendable chain to parent (pick one side)
return node.Val + max(left, right)
dfs(root)
return res
Builds on Diameter:
Diameter returns height, tracks edge count. Max Path Sum returns best chain, tracks best complete path. Same structural pattern.
Init res = MinInt32:
Not 0! An all-negative tree still has a valid answer (the least negative node).
Serialize & Deserialize Binary Tree
O(n) Time / O(n) Space
Goal: Convert a binary tree to a string and back, preserving the exact structure including nulls.
Technique: BFS Level-Order (same as buildTree helper)
Why BFS? Level-order gives a natural positional encoding. For any node dequeued, the next two elements in the string are always its left and right children. This is the same logic as the test helper buildTree([]*int).
The Key Insight:
BFS processes nodes left→right at each level.
When we serialize, we enqueue BOTH children
(including nils) so every node's position is fixed.
When we deserialize, we consume elements in pairs:
dequeue a node → next element = left child
→ element after = right child
This works because the queue order during serialize
matches the queue order during deserialize.
Serialize (Tree → String):
func serialize(root *TreeNode) string:
if root == nil: return "$"
var res strings.Builder
queue := []*TreeNode{root}
for len(queue) > 0:
node := queue[0]; queue = queue[1:]
if node == nil:
res.WriteString("$#") // nil marker + delimiter
continue
res.WriteString(fmt.Sprintf("%d#", node.Val))
queue = append(queue, node.Left, node.Right)
return res.String()
Deserialize (String → Tree):
func deserialize(data string) *TreeNode:
if data == "$": return nil
parts := strings.Split(data, "#")
val, _ := strconv.Atoi(parts[0])
root := &TreeNode{Val: val}
queue := []*TreeNode{root}
idx := 1
for len(queue) > 0:
node := queue[0]; queue = queue[1:]
// Next two elements are this node's children
if idx < len(parts) && parts[idx] != "$":
val, _ := strconv.Atoi(parts[idx])
node.Left = &TreeNode{Val: val}
queue = append(queue, node.Left)
idx++
if idx < len(parts) && parts[idx] != "$":
val, _ := strconv.Atoi(parts[idx])
node.Right = &TreeNode{Val: val}
queue = append(queue, node.Right)
idx++
return root
Why It Works - Pairing Invariant:
1
/ \
2 3 serialize queue order:
/ \ dequeue 1 → enqueue 2, 3
4 5 dequeue 2 → enqueue $, $
dequeue 3 → enqueue 4, 5
String: "1#2#3#$#$#4#5#$#$#$#$#"
deserialize reads pairs from idx:
node 1 → parts[1]=2 (left), parts[2]=3 (right)
node 2 → parts[3]=$ (left), parts[4]=$ (right)
node 3 → parts[5]=4 (left), parts[6]=5 (right)
The queue ensures the pairing order is identical.
DFS Alternative:
Preorder DFS with a global index also works. BFS is more intuitive here because the "next two elements = children" pairing is direct.
Delimiter Choice:
Use a separator (like "#") between tokens. Without it, multi-digit or negative values like "-10" become ambiguous.
Core Patterns Summary
1. Basic DFS (Height/Depth/Size)
Use When: Computing aggregate properties from subtrees.
Template: Base case nil, recurse children, combine with +1 or max or sum.
Examples: Max Depth, Min Depth, Tree Size, Sum of Nodes.
2. DFS with Modification
Use When: Changing tree structure.
Template: Recurse to get modified subtrees, attach/swap at current node.
Examples: Invert Tree, Prune Tree, Flatten to List.
3. DFS with Global State
Use When: Computing one thing (returned) while tracking another (global).
Template: Return local property (height), update global property (diameter/balance).
Examples: Diameter, Balanced Check, Max Path Sum.
4. Parallel DFS (Two Trees)
Use When: Comparing two trees node-by-node.
Template: Check both nil, check one nil, check values, recurse both children.
Examples: Same Tree, Symmetric Tree, Merge Trees.
5. BFS Level-Order
Use When: Need level-by-level processing.
Template: Queue with level-size tracking.
Examples: Level Order Traversal, Right Side View, Level Averages.
6. Composition
Use When: Problem needs a subroutine check at each node.
Template: Outer DFS traverses, inner function validates.
Examples: Subtree Check, Path Sum variants.
7. Reconstruction from Traversals
Use When: Building a tree from two traversal orders.
Template: One traversal identifies root, the other splits left/right. Use subtree size to bridge arrays. Recurse on sub-slices.
Examples: Construct from Preorder+Inorder, Construct from Inorder+Postorder.
Building Blocks:
Master these 7 patterns - medium/hard problems combine them.
Space Complexity: O(h) vs O(n)
O(h) Space where h = height of tree:
- Recursive DFS uses call stack proportional to height
- Best case (balanced): h = log(n)
- Worst case (skewed): h = n
O(n) Space:
- BFS queue can hold entire level
- Widest level in complete tree: ~n/2 nodes
Interview Tip:
Always clarify "O(h)" - interviewers may ask about balanced vs skewed trees.
Common Mistakes
1. Forgetting Base Case
Always handle nil before accessing .Left, .Right, or .Val.
2. Wrong Return vs Track
In diameter/balance: return height (parent needs), track answer (comparing).
3. Depth vs Height Confusion
Depth: Distance from root (root has depth 0 or 1 depending on convention).
Height: Distance to farthest leaf (leaf has height 0 or 1).
4. Edge vs Node Counting
Diameter is edges (left + right heights). Depth is often nodes (add 1).
5. Nil Check Order
// WRONG: p.Val before nil check
if p.Val != q.Val || p == nil ...
// RIGHT: nil check first
if p == nil || q == nil || p.Val != q.Val ...
Preview: Building to Medium Problems
These easy problems establish foundations for harder patterns:
Max Depth → Max Path Sum
Same DFS-with-global-state pattern, but track max sum instead of diameter.
Same Tree → Serialize/Deserialize
If you can compare trees, you can convert to/from string representation.
Construct from Traversals → Postorder Variant
Same reconstruction logic, but with postorder the root is the last element instead of first. Split logic is identical.
Subtree → Lowest Common Ancestor
Both use "search in subtrees, combine at current node" pattern.
BFS Depth → Level Order Variants
Right side view, zigzag traversal - same BFS, different collection logic.
Balanced Check → Validate BST
Both check a property at every node while traversing.
Master the Basics:
Medium problems = combining/extending these exact patterns.