Coding Drills · 06

Binary Trees & BST

Fourteen drills on the structure where recursion stops being a trick and becomes the only sane way to think. Every problem here is answered by deciding what each node needs from its children, what it needs from its ancestors, or which level it lives on — post-order DFS, top-down DFS, or BFS. Each drill comes with a traced tree diagram, complete Java code and the classic pitfalls.

14
Drills
8
Easy
6
Medium
0
Hard
Hub · 01 Arrays & Hashing · 02 Two Pointers · 03 Strings & Sliding Window · 04 Binary Search & Intervals · 05 Linked Lists · 06 Binary Trees & BST · 07 Grids & Matrices · 08 Graphs · 09 Dynamic Programming · 10 Backtracking & Design
01
Chapter One · Core Idea

What a Binary Tree Really Is

4 2 1 3 6 5 7 root leaves (no children) BST: left < node < right

A binary tree is a linked structure where each node has a value and two child references, left and right, either of which may be null. The top node is the root; nodes with no children are leaves. Every node is itself the root of a smaller binary tree — its subtree — and that self-similarity is why almost every tree algorithm is a recursive function that calls itself on node.left and node.right and combines the results.

A binary search tree (BST) adds an ordering invariant: every value in a node's left subtree is smaller than the node, every value in its right subtree is larger. That invariant makes search, insert and delete O(h), where h is the height — O(log n) when balanced, O(n) when the tree degenerates into a chain. It also means an inorder traversal of a BST visits the values in sorted order, a fact several drills exploit.

TermMeaningWhy it matters in drills
Depth of a nodeedges from the root to the nodeBFS levels, zigzag direction
Height of a nodenodes (or edges) on the longest path down to a leafmax depth, balanced check, diameter
h (tree height)O(log n) balanced, O(n) skewedrecursion stack = O(h) extra space
Leafboth children nullpath-sum must stop only at leaves
Full / complete / perfectshape constraintsaffect width of BFS queue (up to n/2)
The node class used in every drill
static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } }

Every Java program below also contains a small build(Integer... vals) helper that constructs a tree from LeetCode's level-order notation (null = missing child), so each main() reproduces the example exactly.

Analogy: A binary tree is a company org chart where each manager has at most two direct reports. To compute anything about the whole company — headcount, the longest reporting chain, whether every team is balanced — the CEO asks each direct report for the answer about their own department, and combines the two replies. Each manager does the same, recursively, until someone with no reports just answers directly.
02
Chapter Two · Mental Model

How to Think Recursively About Trees

Every node is the root of its own subtree
▶
Any property of the tree can be defined in terms of the same property on left and right — the recursive call is the induction step.
The base case is node == null
▶
Define what an empty tree returns (height 0, "is valid" true, "contains target" false) and most special cases disappear.
Information can flow UP (return values) or DOWN (parameters)
▶
Children-to-parent problems (height, balanced, diameter, LCA) are post-order. Ancestor-to-child problems (path sum, BST bounds) are top-down / pre-order.
Some answers are grouped by depth
▶
Recursion naturally goes deep, not wide. For "level by level" use BFS with a queue and freeze queue.size() at the start of each level.
Each node is visited once
▶
Nearly every drill is O(n) time. Space is the recursion stack, O(h): O(log n) for balanced trees, O(n) for a skewed chain.
A function can return one thing but you may need two
▶
Return the value the parent needs (height) and update a field for the global answer (diameter), or encode failure in the return value (-1 for unbalanced).
Which tree technique applies?
Does a node need answers from BOTH children? yes Post-order DFS (return values up) no Does a node need context from its ancestors? yes Top-down DFS (pass state as params) no Is the answer grouped by depth / level? yes BFS + level-size snapshot no Are you comparing two trees (or two halves)? yes Paired recursion f(a, b) no Must you build or rewire the structure? yes Divide by root index / pointer surgery Height, balanced, diameter, LCA → post-order. Path sum, validate BST → top-down. Level order, zigzag → BFS.
03
Chapter Three · Pattern Toolkit

Four Templates for Every Tree Problem

Four templates solve all fourteen drills. The recursive ones are three to six lines each; what changes from problem to problem is only what you return and what you pass down.

Template A — The three DFS orders
Where you "visit" the node relative to the two recursive calls decides the order.
Pseudocode
function dfs(node): if node == null: return visit(node) // PRE-order: node, left, right dfs(node.left) visit(node) // IN-order: left, node, right (sorted for a BST) dfs(node.right) visit(node) // POST-order: left, right, node (children first)
Template A — pre / in / post order on one BST
preorder 4 2 1 3 6 5 7 1 2 3 4 5 6 7 4 2 1 3 6 5 7 inorder 4 2 1 3 6 5 7 4 2 1 3 6 5 7 1 2 3 4 5 6 7 postorder 4 2 1 3 6 5 7 7 3 1 2 6 4 5 1 3 2 5 7 6 4 gold numbers = visit order on the same tree [4,2,6,1,3,5,7]
Template B — Bottom-up (post-order) DFS
Use when a node's answer is a function of its children's answers: height, size, balanced, diameter, LCA.
Pseudocode
function solve(node): if node == null: return BASE // e.g. height 0 L = solve(node.left) R = solve(node.right) updateGlobal(L, R, node) // optional: diameter, LCA return combine(L, R, node) // e.g. 1 + max(L, R)
Template B — heights computed bottom-up on [3,9,20,null,null,15,7]
3 9 20 15 7 h=1 h=1 h=1 h = 1+max(1,1) = 2 h = 1+max(1,2) = 3 answers flow UP: children first, then parent
Template C — Top-down DFS with state
Use when a node needs something only its ancestors know: running sum, depth, the allowed (low, high) window of a BST.
Pseudocode
function solve(node, state): if node == null: return BASE if not valid(node, state): return FAIL newState = update(state, node) // e.g. remaining - node.val return solve(node.left, newState) and/or solve(node.right, newState)
Template C — BST windows passed down on [4,2,6,1,3,5,7]
4 2 1 3 6 5 7 (-∞, +∞) (-∞, 4) (4, +∞) (-∞, 2) (2, 4) (4, 6) (6, +∞) state flows DOWN: each child inherits its parent's window, tightened by the parent's value
Template D — BFS level by level
Use when the answer is organised by depth: level order, zigzag, right side view, minimum depth.
Pseudocode
function levels(root): queue = [root] while queue not empty: size = queue.size() // freeze: nodes of THIS level only repeat size times: node = queue.poll() record(node) push node.left, node.right if not null finishLevel()
Template D — one loop iteration per level on [3,9,20,null,null,15,7]
level 0 level 1 level 2 3 9 20 15 7 queue [3] size 1 → [3] queue [9, 20] size 2 → [9, 20] queue [15, 7] size 2 → [15, 7]
Before writing any tree recursion, answer three questions:
  • What does the function return for null? (This is your base case.)
  • What does each node need from its children, and what does it pass down?
  • Is the answer at the root the final answer, or do I need a global / field for "best seen anywhere"?
04
Drills 51–52 · Traversal

Inorder & Preorder Traversal

Drill 51 — Binary Tree Inorder Traversal
EasyDFS + explicit stackLeetCode 94 ↗
Given the root of a binary tree, return the inorder traversal of its values (left subtree, node, right subtree). Follow-up: do it iteratively.
Example
Input: root = [1,null,2,3] Output: [1,3,2] // 1 has right child 2; 2 has left child 3 Input: root = [] Output: []
Key insight: The recursive version is three lines. The iterative version simulates the call stack: keep pushing left children (those are the calls that have not returned yet); when you can go no further left, pop — that node's left subtree is finished, so visit it and switch to its right subtree.
From brute force to optimal

Recursion is O(n) time and O(h) stack — and it is the right answer unless the interviewer asks for iterative (to avoid stack overflow on skewed trees with 105 nodes). The explicit-stack version has the same bounds but uses heap memory. Morris traversal achieves O(1) extra space by temporarily threading right pointers back to ancestors — worth naming as a follow-up, rarely required.

Walkthrough
Iterative inorder on [1,null,2,3]: dive left, pop, visit, go right
1 2 3 ① ② ③ output: [1, 3, 2] action stack (top right) output push 1 [1] — pop 1, visit [] 1 curr = 2: push 2, push 3 [2, 3] 1 pop 3, visit [2] 1 3 pop 2, visit [] 1 3 2 curr = null, stack empty done 1 3 2
Java — complete solution with main()
import java.util.*; public class InorderTraversal { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Iterative: push the whole left spine, pop, visit, then go right. // O(n) time, O(h) space for the explicit stack. static List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { // 1. dive left as far as possible stack.push(curr); curr = curr.left; } curr = stack.pop(); // 2. leftmost unvisited node result.add(curr.val); // 3. visit it curr = curr.right; // 4. then explore its right subtree } return result; } // Recursive reference version static void inorder(TreeNode node, List<Integer> out) { if (node == null) return; inorder(node.left, out); out.add(node.val); inorder(node.right, out); } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { TreeNode root = build(1, null, 2, 3); System.out.println(inorderTraversal(root)); // [1, 3, 2] List<Integer> rec = new ArrayList<>(); inorder(build(4, 2, 6, 1, 3, 5, 7), rec); System.out.println(rec); // [1, 2, 3, 4, 5, 6, 7] } }
ApproachTimeSpaceNotes
RecursiveO(n)O(h) stacksimplest
Iterative with stackO(n)O(h)no recursion depth limit
Morris traversalO(n)O(1)temporarily modifies the tree
⚠ Common bugs & edge cases:
  • Outer loop must be while (curr != null || !stack.isEmpty()) — checking only the stack stops before exploring the root's right subtree.
  • Use ArrayDeque, not the legacy synchronised Stack class.
  • For a BST, inorder gives sorted order — the basis of "kth smallest" and an alternative BST validation.
Drill 52 — Binary Tree Preorder Traversal
EasyDFS + explicit stackLeetCode 144 ↗
Given the root of a binary tree, return the preorder traversal of its values (node, left subtree, right subtree).
Example
Input: root = [1,null,2,3] Output: [1,2,3] Input: root = [4,2,6,1,3,5,7] Output: [4,2,1,3,6,5,7]
Key insight: Preorder visits a node the moment it is reached, so the iterative version is simpler than inorder: pop, record, push children. A stack is LIFO, so push the right child first — the left child, pushed last, is popped next.
From brute force to optimal

As with inorder, recursion is O(n)/O(h) and perfectly acceptable; the iterative form avoids recursion-depth limits. Preorder is the order used to serialise a tree (copy it, send it over the network) because the root comes first — Drill 63 rebuilds a tree from exactly this sequence.

Walkthrough
Iterative preorder on [4,2,6,1,3,5,7]: push right before left
4 2 1 3 6 5 7 1 2 3 4 5 6 7 action stack (top right) output pop 4 → push 6, 2 [6, 2] 4 pop 2 → push 3, 1 [6, 3, 1] 4 2 pop 1 (leaf) [6, 3] 4 2 1 pop 3 (leaf) [6] 4 2 1 3 pop 6 → push 7, 5 [7, 5] 4 2 1 3 6 pop 5 [7] ... 6 5 pop 7 [] ... 6 5 7 result: [4, 2, 1, 3, 6, 5, 7]
Java — complete solution with main()
import java.util.*; public class PreorderTraversal { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Iterative: pop, visit, push RIGHT then LEFT (so left is popped first). // O(n) time, O(h) space. static List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); if (node.right != null) stack.push(node.right); if (node.left != null) stack.push(node.left); } return result; } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { System.out.println(preorderTraversal(build(1, null, 2, 3))); // [1, 2, 3] System.out.println(preorderTraversal(build(4, 2, 6, 1, 3, 5, 7))); // [4, 2, 1, 3, 6, 5, 7] System.out.println(preorderTraversal(null)); // [] } }
ApproachTimeSpaceNotes
RecursiveO(n)O(h) stack
Iterative with stackO(n)O(h)right pushed before left
⚠ Common bugs & edge cases:
  • Pushing left before right yields node, right, left — a mirrored preorder.
  • Pushing null children and then dereferencing them — check before pushing.
  • Reversing "node, right, left" gives postorder (left, right, node) — a common trick for iterative postorder.
05
Drills 53–54 · Recursion Basics

Maximum Depth & Same Tree

Drill 53 — Maximum Depth of Binary Tree
Easypost-order DFSLeetCode 104 ↗
Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to the farthest leaf.
Example
Input: root = [3,9,20,null,null,15,7] Output: 3 Input: root = [] Output: 0
Key insight: The depth of a tree is one (for the root) plus the depth of its deeper subtree. That sentence is the code. An empty tree has depth 0, which is the base case.
From brute force to optimal

There is no meaningful brute force — any correct solution must look at every node, so O(n) is optimal. The choice is DFS (O(h) stack, one line) versus BFS that counts levels (O(w) queue, where w can be n/2 for a complete tree). For a skewed tree of 105 nodes, BFS avoids StackOverflowError.

Walkthrough
maxDepth on [3,9,20,null,null,15,7] — answers bubble up
3 9 20 15 7 returns 1 returns 1 returns 1 1 + max(1,1) = 2 1 + max(1,2) = 3 call order (post-order): maxDepth(9) → 1 maxDepth(15) → 1 maxDepth(7) → 1 maxDepth(20) → 2 maxDepth(3) → 3 red edges: one longest root-to-leaf path (3 → 20 → 15)
Java — complete solution with main()
import java.util.*; public class MaximumDepth { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Post-order recursion: depth = 1 + deeper child. O(n) time, O(h) stack. static int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } // BFS alternative: count the levels. O(n) time, O(w) queue. static int maxDepthBfs(TreeNode root) { if (root == null) return 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int depth = 0; while (!queue.isEmpty()) { depth++; for (int size = queue.size(); size > 0; size--) { TreeNode node = queue.poll(); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } } return depth; } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { TreeNode root = build(3, 9, 20, null, null, 15, 7); System.out.println(maxDepth(root)); // 3 System.out.println(maxDepthBfs(root)); // 3 System.out.println(maxDepth(null)); // 0 } }
ApproachTimeSpaceNotes
Recursive DFSO(n)O(h)one line
BFS level countO(n)O(w)no recursion
⚠ Common bugs & edge cases:
  • Returning -1 for null switches the definition to "edges" — the LeetCode answer counts nodes.
  • Minimum depth (LC 111) is NOT 1 + min(L, R): a node with one null child is not a leaf, so take the non-null side.
Drill 54 — Same Tree
Easypaired recursionLeetCode 100 ↗
Given the roots of two binary trees p and q, return true if they are structurally identical and every corresponding node has the same value.
Example
Input: p = [1,2,3], q = [1,2,3] Output: true Input: p = [1,2], q = [1,null,2] Output: false Input: p = [1,2,1], q = [1,1,2] Output: false
Key insight: Walk both trees with one recursive function that takes a pair of nodes. Three cases cover everything: both null (equal), exactly one null (shape differs), both present (compare values, then recurse on left-left and right-right).
From brute force to optimal

Serialising both trees (with null markers) and comparing the strings works in O(n) but allocates O(n) memory and is error-prone without the markers ([1,2] and [1,null,2] serialise identically without them). Paired recursion stops at the first mismatch: O(min(n, m)) time, O(h) stack.

Walkthrough
Lock-step comparison: values match AND shapes match
p = [1,2,3] 1 2 3 q = [1,2,3] 1 2 3 same → true p = [1,2] 1 2 q = [1,null,2] 1 2 p.left = 2 but q.left = null → one null, one not → false
Callp nodeq nodeResult
isSame(1, 1)11values equal → check children
isSame(2, 2)22equal; both children null → true
isSame(3, 3)33equal; both children null → true
back at roottrue && true && true → true
Java — complete solution with main()
import java.util.*; public class SameTree { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Compare in lock-step: both null, one null, or values + both subtrees. // O(min(n, m)) time, O(h) stack. static boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; if (p == null || q == null) return false; return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { System.out.println(isSameTree(build(1, 2, 3), build(1, 2, 3))); // true System.out.println(isSameTree(build(1, 2), build(1, null, 2))); // false (shape) System.out.println(isSameTree(build(1, 2, 1), build(1, 1, 2))); // false (values) } }
ApproachTimeSpaceNotes
Serialise both, compare stringsO(n+m)O(n+m)needs null markers
Paired recursionO(min(n,m))O(h)short-circuits
⚠ Common bugs & edge cases:
  • Checking only values, not structure: forgetting the "exactly one null" case.
  • Comparing traversal lists without null markers — different shapes can give identical sequences.
  • Using p == q (reference equality) on non-null nodes: two separate trees never share nodes.
06
Drill 55 · Mirror Recursion

Symmetric Tree

Drill 55 — Symmetric Tree
Easypaired recursion (mirror)LeetCode 101 ↗
Given the root of a binary tree, check whether it is a mirror of itself (symmetric around its centre).
Example
Input: root = [1,2,2,3,4,4,3] Output: true Input: root = [1,2,2,null,3,null,3] Output: false
Key insight: This is Same Tree with crossed wires. Two subtrees are mirrors if their roots match, the outer children match (left.left with right.right) and the inner children match (left.right with right.left). Fold the tree along the vertical axis and check that every node lands on an equal node.
From brute force to optimal

One brute-force idea: build a mirrored copy of the tree, then run Same Tree against the original — O(n) time but O(n) extra nodes. Another: level-order with null markers and check each level is a palindrome — O(n) time, O(w) space. Mirror recursion compares the pairs directly: O(n) time, O(h) stack, no allocation. An iterative version pushes node pairs onto a queue in the same crossed order.

Walkthrough
Symmetric on [1,2,2,3,4,4,3]: compare mirror positions, not same positions
1 2 3 4 2 4 3 outer pair (3,3) inner pair (4,4) isMirror(2, 2) values equal isMirror(L.left=3, R.right=3) isMirror(L.right=4, R.left=4) all leaves: null/null pairs → true result: true
Java — complete solution with main()
import java.util.*; public class SymmetricTree { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // A tree is symmetric if its left and right subtrees are mirrors. // O(n) time, O(h) stack. static boolean isSymmetric(TreeNode root) { return root == null || isMirror(root.left, root.right); } static boolean isMirror(TreeNode a, TreeNode b) { if (a == null && b == null) return true; if (a == null || b == null) return false; return a.val == b.val && isMirror(a.left, b.right) // outer pair && isMirror(a.right, b.left); // inner pair } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { System.out.println(isSymmetric(build(1, 2, 2, 3, 4, 4, 3))); // true System.out.println(isSymmetric(build(1, 2, 2, null, 3, null, 3))); // false } }
ApproachTimeSpaceNotes
Mirror copy + Same TreeO(n)O(n)allocates a second tree
Level palindromes (BFS)O(n)O(w)needs null markers
Mirror recursionO(n)O(h)no allocation
⚠ Common bugs & edge cases:
  • Recursing on (left.left, right.left) — that tests "same", not "mirror".
  • Checking only that each level's VALUES read as a palindrome while ignoring nulls: [1,2,2,null,3,null,3] has levels [1],[2,2],[3,3] yet is not symmetric.
  • Calling isMirror(root, root) is correct but does every comparison twice; isMirror(root.left, root.right) halves the work.
07
Drill 56 · Post-order + Sentinel

Balanced Binary Tree

Drill 56 — Balanced Binary Tree
Easypost-order DFS + sentinelLeetCode 110 ↗
Given a binary tree, determine if it is height-balanced: for every node, the heights of its left and right subtrees differ by at most one.
Example
Input: root = [3,9,20,null,null,15,7] Output: true Input: root = [1,2,2,3,3,null,null,4,4] Output: false Input: root = [] Output: true
Key insight: Each node needs two facts from each child: "are you balanced?" and "how tall are you?". Pack both into one int — the height, or -1 meaning "unbalanced somewhere below" — and the check becomes a single post-order pass.
From brute force to optimal

The top-down version calls height() on both children at every node and then recurses: correct, but heights are recomputed for each ancestor, giving O(n log n) on balanced trees and O(n2) on skewed ones. The bottom-up version computes each height once and short-circuits on the first failure: O(n) time, O(h) stack.

Walkthrough
Balanced check: heights bottom-up, -1 as the failure signal
balanced 3 9 20 15 7 L1 R2 → h3 h1 L1 R1 → h2 h1 h1 not balanced 1 2 3 4 4 3 2 L3 R1 → |3-1| = 2 → -1 L2 R1 → h3 h2 h1 height() returns -1 the moment any subtree is unbalanced; the -1 propagates straight to the root.
Java — complete solution with main()
import java.util.*; public class BalancedBinaryTree { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Bottom-up: return the height, or -1 as soon as any subtree is unbalanced. // Every node is visited once: O(n) time, O(h) stack. static boolean isBalanced(TreeNode root) { return height(root) != -1; } static int height(TreeNode node) { if (node == null) return 0; int left = height(node.left); if (left == -1) return -1; // short-circuit int right = height(node.right); if (right == -1) return -1; if (Math.abs(left - right) > 1) return -1; // this node breaks the rule return 1 + Math.max(left, right); } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { System.out.println(isBalanced(build(3, 9, 20, null, null, 15, 7))); // true System.out.println(isBalanced(build(1, 2, 2, 3, 3, null, null, 4, 4))); // false System.out.println(isBalanced(null)); // true } }
ApproachTimeSpaceNotes
Top-down: height() at every nodeO(n log n) – O(n²)O(h)recomputes heights
Bottom-up with -1 sentinelO(n)O(h)each node once
⚠ Common bugs & edge cases:
  • Checking balance only at the root: [1,2,2,3,null,null,3,4,null,null,4] has equal root subtree heights but is unbalanced deeper down.
  • Forgetting to propagate -1 from a child — a later Math.max silently swallows it.
  • "Balanced" here is the AVL definition (difference ≤ 1 at every node), not "complete" or "perfect".
08
Drill 57 · Top-down DFS

Path Sum

Drill 57 — Path Sum
Easytop-down DFSLeetCode 112 ↗
Given the root of a binary tree and an integer targetSum, return true if there is a root-to-leaf path whose values add up to targetSum.
Example
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true // 5 + 4 + 11 + 2 = 22 Input: root = [1,2], targetSum = 1 Output: false // node 1 is not a leaf, so the path [1] does not count
Key insight: Carry the remaining amount down the tree: subtract each node's value on the way. The question is only asked at a leaf — "is the remainder exactly zero here?". Values can be negative, so you cannot prune early when the remainder goes below zero.
From brute force to optimal

A brute force collects every root-to-leaf path into a list and sums each — O(n·h) time and memory for the path copies. Passing the remainder as a parameter makes each node O(1) work: O(n) time, O(h) stack, and the || stops as soon as one valid path is found.

Walkthrough
Path Sum on [5,4,8,11,null,13,4,7,2,null,null,null,1], target 22
5 4 11 7 2 8 13 4 1 rem 22-5 = 17 rem 17-4 = 13 rem 13-11 = 2 rem 17-8 = 9 rem 9-4 = 5 2-2 = 0 ✓ 2-7 ≠ 0 leaf: 9-13 ≠ 0 leaf: 5-1 ≠ 0 target = 22. DFS explores left first and returns true at leaf 2; the || short-circuits, so the right subtree is never visited.
Java — complete solution with main()
import java.util.*; public class PathSum { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Subtract on the way down; check only at LEAVES. O(n) time, O(h) stack. static boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; int remaining = targetSum - root.val; if (root.left == null && root.right == null) return remaining == 0; return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining); } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { TreeNode root = build(5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1); System.out.println(hasPathSum(root, 22)); // true (5 -> 4 -> 11 -> 2) System.out.println(hasPathSum(build(1, 2, 3), 5)); // false System.out.println(hasPathSum(build(1, 2), 1)); // false (1 is not a leaf) } }
ApproachTimeSpaceNotes
Enumerate all paths, sum eachO(n·h)O(n·h)copies paths
Top-down remainderO(n)O(h)short-circuits on success
⚠ Common bugs & edge cases:
  • Checking remaining == 0 at a null child instead of at a leaf: for [1,2] and target 1 that wrongly returns true via the missing right child.
  • Pruning when remaining < 0 — node values may be negative.
  • Empty tree with targetSum 0 must return false: there is no root-to-leaf path at all.
  • Follow-ups: Path Sum II (return all paths — backtracking with a list), Path Sum III (any downward path — prefix sums + HashMap).
09
Drill 58 · Return One, Record Another

Diameter of Binary Tree

Drill 58 — Diameter of Binary Tree
Easypost-order DFS + globalLeetCode 543 ↗
Return the length of the diameter of a binary tree: the number of edges on the longest path between any two nodes. The path may or may not pass through the root.
Example
Input: root = [1,2,3,4,5] Output: 3 // path 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3) Input: root = [1,2] Output: 1
Key insight: Every path has one highest node where it "bends". The longest path bending at node X has length height(X.left) + height(X.right). So compute heights bottom-up (Template B) and, at every node, offer left + right as a candidate for the global maximum. The function returns height (what the parent can extend) but records diameter (what is complete here).
From brute force to optimal

Calling height() separately at every node to compute left + right is O(n2) on skewed trees. Merging the two jobs into one post-order pass computes each height exactly once: O(n) time, O(h) stack.

Walkthrough
Diameter of [1,2,3,4,5]: every node proposes left + right
1 2 4 5 3 h=1, through=0 h=1, through=0 h=2, through=1+1=2 h=1, through=0 h=3, through=2+1=3 ← best best after each return: node 4 → best = 0 node 5 → best = 0 node 2 → best = 2 node 3 → best = 2 node 1 → best = 3 longest path (red): 4 → 2 → 1 → 3 = 3 edges
Java — complete solution with main()
import java.util.*; public class DiameterOfBinaryTree { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } private static int best; // longest path seen so far, in edges // Each node returns its height; the path THROUGH it is left + right. // O(n) time, O(h) stack. static int diameterOfBinaryTree(TreeNode root) { best = 0; height(root); return best; } static int height(TreeNode node) { if (node == null) return 0; int left = height(node.left); int right = height(node.right); best = Math.max(best, left + right); // path bending at this node return 1 + Math.max(left, right); // what the parent can extend } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { System.out.println(diameterOfBinaryTree(build(1, 2, 3, 4, 5))); // 3 (4 -> 2 -> 1 -> 3) System.out.println(diameterOfBinaryTree(build(1, 2))); // 1 } }
ApproachTimeSpaceNotes
height() called at every nodeO(n²) worstO(h)recomputes
Single post-order passO(n)O(h)height returned, diameter recorded
⚠ Common bugs & edge cases:
  • Returning height(root.left) + height(root.right) only at the root — the longest path may bend lower down, entirely inside one subtree.
  • Mixing up nodes and edges: diameter counts edges, so with height counted in nodes, left + right is already the edge count.
  • A static field must be reset before each call (as in the solution), or repeated calls leak the previous answer.
10
Drills 59–60 · BFS

Level Order & Zigzag Traversal

Drill 59 — Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its values: left to right, level by level, one list per level.
Example
Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]] Input: root = [] Output: []
Key insight: A FIFO queue naturally processes nodes in order of distance from the root. The only trick is knowing where one level ends: at the start of each outer iteration, the queue contains exactly the current level, so snapshot size = queue.size() and poll that many.
From brute force to optimal

DFS can also produce levels by passing depth and appending to result.get(depth) — O(n) time, O(h) stack, and a handy alternative. BFS is the idiomatic answer: O(n) time, O(w) queue where w is the maximum width (up to n/2 in the last level of a complete tree).

Walkthrough
Level order on [3,9,20,null,null,15,7]: one outer iteration per level
L0 L1 L2 3 9 20 15 7 size poll → offer level list 1 3 → 9, 20 [3] 2 9 → —; 20 → 15, 7 [9, 20] 2 15 → —; 7 → — [15, 7] result: [[3], [9, 20], [15, 7]]
Java — complete solution with main()
import java.util.*; public class LevelOrderTraversal { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // BFS with a level-size snapshot. O(n) time, O(w) queue (w = max width). static List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); // freeze the size of THIS level List<Integer> level = new ArrayList<>(size); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); } return result; } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { System.out.println(levelOrder(build(3, 9, 20, null, null, 15, 7))); // [[3], [9, 20], [15, 7]] System.out.println(levelOrder(null)); // [] } }
ApproachTimeSpaceNotes
DFS with depth indexO(n)O(h)result.get(depth).add(val)
BFS + level-size snapshotO(n)O(w)idiomatic
⚠ Common bugs & edge cases:
  • Using queue.size() directly in the for-loop condition — it changes as children are added, mixing levels.
  • Offering null children and then calling node.val on them.
  • Using Stack/push instead of a queue gives a DFS order, not BFS.
  • Same template solves Right Side View (last of each level), Average of Levels, and Minimum Depth (first leaf found).
Drill 60 — Binary Tree Zigzag Level Order Traversal
MediumBFS + dequeLeetCode 103 ↗
Return the zigzag level order traversal: level 0 left-to-right, level 1 right-to-left, level 2 left-to-right, and so on.
Example
Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]] Input: root = [1,2,3,4,5,6,7] Output: [[1],[3,2],[4,5,6,7]]
Key insight: Do not change the order in which nodes are visited — always enqueue left then right, exactly as in Drill 59. Change only how values are written: on reversed levels, insert each value at the front of the level list. A LinkedList makes addFirst O(1).
From brute force to optimal

The simplest correct approach is Drill 59 plus Collections.reverse(level) on odd levels — still O(n) overall, since each value is reversed once. Writing into a deque avoids the extra pass. Trying to alternate the order in which children are enqueued is the classic wrong turn: it scrambles the next level.

Walkthrough
Zigzag on [1,2,3,4,5,6,7]: same BFS, alternate which end of the list you write to
1 2 4 5 3 6 7 L0: addLast(1) → [1] L1: addFirst(2), addFirst(3) → [3, 2] L2: addLast 4, 5, 6, 7 → [4, 5, 6, 7] result: [[1], [3, 2], [4, 5, 6, 7]]
Java — complete solution with main()
import java.util.*; public class ZigzagLevelOrder { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Same BFS, but write each value into a deque from the left or the right. // O(n) time, O(w) space; no reversal pass needed. static List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean leftToRight = true; while (!queue.isEmpty()) { int size = queue.size(); LinkedList<Integer> level = new LinkedList<>(); for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); if (leftToRight) level.addLast(node.val); else level.addFirst(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } result.add(level); leftToRight = !leftToRight; } return result; } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { System.out.println(zigzagLevelOrder(build(3, 9, 20, null, null, 15, 7))); // [[3], [20, 9], [15, 7]] System.out.println(zigzagLevelOrder(build(1, 2, 3, 4, 5, 6, 7))); // [[1], [3, 2], [4, 5, 6, 7]] } }
ApproachTimeSpaceNotes
BFS + Collections.reverse on odd levelsO(n)O(w)fine, one extra pass per level
BFS + addFirst / addLastO(n)O(w)no reversal
Two stacksO(n)O(w)works, more bookkeeping
⚠ Common bugs & edge cases:
  • Swapping the order children are enqueued on alternate levels — the level after next comes out in the wrong order.
  • Using ArrayList.add(0, x) for front insertion: O(level size) per insert, O(w²) per level.
  • Off-by-one on direction: level 0 (the root) is left-to-right.
11
Drill 61 · Post-order Search

Lowest Common Ancestor

Drill 61 — Lowest Common Ancestor of a Binary Tree
Mediumpost-order DFSLeetCode 236 ↗
Given a binary tree and two nodes p and q that both exist in it, return their lowest common ancestor: the deepest node that has both p and q as descendants (a node counts as a descendant of itself).
Example
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Input: same tree, p = 6, q = 4 Output: 5 Input: same tree, p = 5, q = 4 Output: 5 // 5 is an ancestor of 4, and of itself
Key insight: Ask each subtree one question: "did you find p or q?" — returning the node found (or null). If a node receives a non-null answer from both sides, p and q are split across it, so it is the LCA. If only one side answers, pass that answer upward. Returning early when root == p handles the "one is the ancestor of the other" case for free.
From brute force to optimal

The two-path approach records the root-to-p and root-to-q paths (DFS with backtracking) and returns the last common node — O(n) time but O(n) for the paths and two traversals. A parent-pointer map plus an ancestor set also works in O(n) space. The single post-order pass is O(n) time, O(h) stack, and is the standard interview answer. For a BST (LC 235) you can do better: walk down from the root, O(h), using the ordering.

Walkthrough
LCA of 6 and 4 in [3,5,1,6,2,0,8,null,null,7,4] → 5
3 5 6 2 7 4 1 0 8 p = 6 → 6 null q = 4 → 4 null + 4 → returns 4 6 + 4 → BOTH → 5 neither p nor q → null 5 + null → returns 5 Query p = 6, q = 4. Node 5 is the first node to hear back from both sides, so it is the LCA; ancestors just pass it upward.
Java — complete solution with main()
import java.util.*; public class LowestCommonAncestor { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Return p or q if found below; the first node that hears back from // BOTH sides is the LCA. O(n) time, O(h) stack. static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; // split point return (left != null) ? left : right; // bubble up what we found } static TreeNode find(TreeNode node, int val) { if (node == null || node.val == val) return node; TreeNode left = find(node.left, val); return (left != null) ? left : find(node.right, val); } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { TreeNode root = build(3, 5, 1, 6, 2, 0, 8, null, null, 7, 4); System.out.println(lowestCommonAncestor(root, find(root, 5), find(root, 1)).val); // 3 System.out.println(lowestCommonAncestor(root, find(root, 6), find(root, 4)).val); // 5 System.out.println(lowestCommonAncestor(root, find(root, 5), find(root, 4)).val); // 5 (a node is its own ancestor) } }
ApproachTimeSpaceNotes
Store both root-to-node pathsO(n)O(n)two traversals
Parent map + ancestor setO(n)O(n)iterative
Single post-order DFSO(n)O(h)standard answer
⚠ Common bugs & edge cases:
  • Comparing by value instead of reference when values may repeat.
  • Continuing to search below p after finding it — unnecessary, since if q is below p the answer is p anyway.
  • This version assumes both nodes exist. If one might be missing, you must count how many were actually found before trusting the result.
12
Drill 62 · Top-down Bounds

Validate Binary Search Tree

Drill 62 — Validate Binary Search Tree
Mediumtop-down DFS with boundsLeetCode 98 ↗
Given the root of a binary tree, determine if it is a valid BST: every node's left subtree contains only values strictly less than the node, its right subtree only values strictly greater, and both subtrees are BSTs themselves.
Example
Input: root = [2,1,3] Output: true Input: root = [5,1,4,null,null,3,6] Output: false // 4 is in the right subtree of 5 but 4 &lt; 5 Input: root = [5,4,6,null,null,3,7] Output: false // every parent/child pair looks fine, but 3 &lt; 5 in 5's right subtree
Key insight: The BST rule is about whole subtrees, not just parent and child. Each node inherits an open interval (low, high) from its ancestors: going left tightens the upper bound to the parent's value, going right tightens the lower bound. A node is valid only if it lies strictly inside its window.
From brute force to optimal

Brute force: for every node, scan its entire left subtree for the max and right subtree for the min — O(n2) on skewed trees. The window method is O(n) time, O(h) stack. Equivalent alternative: an inorder traversal must be strictly increasing — keep the previous value and compare (also O(n), and it reuses Drill 51).

Walkthrough
Validate [5,4,6,null,null,3,7]: windows catch what parent-child checks miss
5 4 6 3 7 (-∞, +∞) ✓ (-∞, 5) ✓ (5, +∞) ✓ (5, 6) ✗ 3 ≤ 5 (6, +∞) local check (wrong): every parent/child pair is ordered: 4 < 5 < 6 and 3 < 6 < 7 → wrongly says true window check (right): 3 sits in 5's RIGHT subtree, so it must be > 5 → false
Java — complete solution with main()
import java.util.*; public class ValidateBST { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Every node must lie strictly inside the (low, high) window inherited from // its ancestors. long bounds avoid the Integer.MIN_VALUE / MAX_VALUE trap. // O(n) time, O(h) stack. static boolean isValidBST(TreeNode root) { return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } static boolean valid(TreeNode node, long low, long high) { if (node == null) return true; if (node.val <= low || node.val >= high) return false; return valid(node.left, low, node.val) // left: tighten the upper bound && valid(node.right, node.val, high); // right: tighten the lower bound } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { System.out.println(isValidBST(build(2, 1, 3))); // true System.out.println(isValidBST(build(5, 1, 4, null, null, 3, 6))); // false (4 < 5 in right subtree) System.out.println(isValidBST(build(5, 4, 6, null, null, 3, 7))); // false (3 is below 5 but in its right subtree) System.out.println(isValidBST(build(Integer.MAX_VALUE))); // true } }
ApproachTimeSpaceNotes
Max/min of each subtree per nodeO(n²) worstO(h)
Top-down (low, high) windowO(n)O(h)long bounds
Inorder must be strictly increasingO(n)O(h)track previous value
⚠ Common bugs & edge cases:
  • Only comparing a node with its direct children — fails on [5,4,6,null,null,3,7].
  • Using int bounds initialised to Integer.MIN_VALUE/MAX_VALUE: a node holding exactly that value is then rejected. Use long or nullable Integer bounds.
  • Using <=/>= loosely: duplicates are invalid in this problem, so the checks must be strict.
13
Drill 63 · Divide & Conquer

Construct Tree from Preorder & Inorder

Drill 63 — Construct Binary Tree from Preorder and Inorder Traversal
Mediumdivide & conquer + index mapLeetCode 105 ↗
Given two integer arrays preorder and inorder of the same tree (all values unique), construct and return the binary tree.
Example
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Input: preorder = [-1], inorder = [-1] Output: [-1]
Key insight: Preorder tells you who the root is (always the next unused element). Inorder tells you how many nodes go left and right of it (everything before the root's position is the left subtree). Recurse on the two inorder ranges, consuming preorder left-to-right — and because preorder lists the whole left subtree before the right, you must build left first.
From brute force to optimal

The direct approach scans inorder for the root on every call and copies sub-arrays with Arrays.copyOfRange — O(n2) time on skewed trees and O(n2) memory in copies. A HashMap from value to inorder index makes the lookup O(1), and passing index bounds instead of copies removes the allocation: O(n) time, O(n) space for the map plus O(h) stack.

Walkthrough
Rebuild from preorder [3,9,20,15,7] and inorder [9,3,15,20,7]
preorder 3 9 20 15 7 inorder 9 3 15 20 7 left root right subtree preIdx 0: root 3, inorder pos 1 left = in[0..0], right = in[2..4] preIdx 1: root 9, pos 0 left = in[0..-1] ∅, right = in[1..0] ∅ preIdx 2: root 20, pos 3 left = in[2..2], right = in[4..4] preIdx 3: root 15, pos 2 leaf preIdx 4: root 7, pos 4 leaf 3 9 20 15 7 result
Java — complete solution with main()
import java.util.*; public class ConstructFromPreIn { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } private static int preIdx; private static Map<Integer, Integer> inPos; // preorder[preIdx] is always the next root; its position in inorder splits // the remaining values into left and right subtrees. // O(n) time with the index map, O(n) space. static TreeNode buildTree(int[] preorder, int[] inorder) { preIdx = 0; inPos = new HashMap<>(); for (int i = 0; i < inorder.length; i++) inPos.put(inorder[i], i); return construct(preorder, 0, inorder.length - 1); } static TreeNode construct(int[] preorder, int inLo, int inHi) { if (inLo > inHi) return null; int rootVal = preorder[preIdx++]; TreeNode root = new TreeNode(rootVal); int mid = inPos.get(rootVal); root.left = construct(preorder, inLo, mid - 1); // MUST build left first: root.right = construct(preorder, mid + 1, inHi); // preorder lists left before right return root; } static List<Integer> levelOrder(TreeNode root) { List<Integer> out = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); if (root != null) queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); out.add(node.val); if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } return out; } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { int[] preorder = {3, 9, 20, 15, 7}; int[] inorder = {9, 3, 15, 20, 7}; TreeNode root = buildTree(preorder, inorder); System.out.println(levelOrder(root)); // [3, 9, 20, 15, 7] System.out.println(root.right.left.val); // 15 } }
ApproachTimeSpaceNotes
Linear search + array copiesO(n²)O(n²)copyOfRange each call
Index map + bounds + shared preIdxO(n)O(n)map + O(h) stack
⚠ Common bugs & edge cases:
  • Building the right subtree before the left while consuming preorder sequentially — the indices go out of sync.
  • Forgetting to reset the shared preIdx between calls when it is a static field.
  • The algorithm requires unique values; with duplicates the inorder split is ambiguous.
  • Variant LC 106 (inorder + postorder): consume postorder from the END and build the RIGHT subtree first.
14
Drill 64 · Pointer Surgery

Flatten Binary Tree to Linked List

Drill 64 — Flatten Binary Tree to Linked List
Mediumpointer surgery (Morris)LeetCode 114 ↗
Flatten a binary tree into a "linked list" in place: use the right pointer as next, set every left to null, and the order must match a preorder traversal. Follow-up: O(1) extra space.
Example
Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6] // i.e. 1 → 2 → 3 → 4 → 5 → 6 along right pointers
Key insight: In preorder, a node's right subtree comes right after the last node of its left subtree — the rightmost node there. So for each node with a left child: hang the right subtree off that rightmost node, move the left subtree into the right slot, clear left, and step right. No stack, no recursion.
From brute force to optimal

The easy way collects nodes in preorder into a list and relinks them — O(n) time and O(n) space. The reverse-preorder recursion (right, left, then node, with a prev pointer) is elegant and O(n) time but O(h) stack. The Morris-style splice is O(n) time — each "find rightmost" walk covers edges that are never walked again — and O(1) space.

Walkthrough
Flatten [1,2,5,3,4,null,6] in place — Morris-style splicing
before 1 2 3 4 5 6 after curr = 1 1 2 3 4 5 6 pred of 1 = 4 (rightmost of left) 4.right = 5; 1.right = 2; 1.left = null after curr = 2 (done) 1 right 2 right 3 right 4 right 5 right 6 right pred of 2 = 3; 3.right = 4
currhas left?pred (rightmost of left)RewireChain so far
1yes (2)44.right = 5; 1.right = 2; 1.left = null1 → 2 …
2yes (3)33.right = 4; 2.right = 3; 2.left = null1 → 2 → 3 → 4 → 5 → 6
3, 4, 5, 6no—just move rightdone
Java — complete solution with main()
import java.util.*; public class FlattenBinaryTree { static class TreeNode { int val; TreeNode left, right; TreeNode(int val) { this.val = val; } } // Morris-style: for each node with a left subtree, find the rightmost node // of that subtree (the preorder predecessor of node.right), hang node.right // there, then move the left subtree to the right. // O(n) time (each edge walked at most twice), O(1) extra space. static void flatten(TreeNode root) { TreeNode curr = root; while (curr != null) { if (curr.left != null) { TreeNode pred = curr.left; while (pred.right != null) pred = pred.right; pred.right = curr.right; // 1. old right subtree goes after the left subtree curr.right = curr.left; // 2. left subtree moves to the right curr.left = null; // 3. clear the left pointer } curr = curr.right; } } // Recursive alternative (reverse preorder: right, left, node): O(h) stack private static TreeNode prev; static void flattenRecursive(TreeNode node) { if (node == null) return; flattenRecursive(node.right); flattenRecursive(node.left); node.right = prev; node.left = null; prev = node; } static String chain(TreeNode root) { StringBuilder sb = new StringBuilder(); for (TreeNode n = root; n != null; n = n.right) { if (n.left != null) return "left pointer not cleared!"; sb.append(n.val).append(n.right != null ? " -> " : ""); } return sb.toString(); } // Builds a tree from LeetCode-style level order (null = missing child) static TreeNode build(Integer... vals) { if (vals.length == 0 || vals[0] == null) return null; TreeNode root = new TreeNode(vals[0]); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int i = 1; while (!queue.isEmpty() && i < vals.length) { TreeNode node = queue.poll(); if (i < vals.length && vals[i] != null) { node.left = new TreeNode(vals[i]); queue.offer(node.left); } i++; if (i < vals.length && vals[i] != null) { node.right = new TreeNode(vals[i]); queue.offer(node.right); } i++; } return root; } public static void main(String[] args) { TreeNode root = build(1, 2, 5, 3, 4, null, 6); flatten(root); System.out.println(chain(root)); // 1 -> 2 -> 3 -> 4 -> 5 -> 6 TreeNode again = build(1, 2, 5, 3, 4, null, 6); prev = null; flattenRecursive(again); System.out.println(chain(again)); // 1 -> 2 -> 3 -> 4 -> 5 -> 6 } }
ApproachTimeSpaceNotes
Preorder into a list, relinkO(n)O(n)
Reverse preorder recursionO(n)O(h)right, left, node + prev
Morris-style spliceO(n)O(1)follow-up answer
⚠ Common bugs & edge cases:
  • Forgetting curr.left = null — the result still has left children and fails the check.
  • Moving the left subtree to the right before saving the old right subtree — it becomes unreachable.
  • Recursive version: visiting left before right with a prev pointer overwrites node.right before it is explored.
15
Chapter Fifteen · Summary

All Fourteen Drills at a Glance

Every drill on this page is O(n) time — each node is visited a constant number of times. The space column is where solutions differ: O(h) for recursion (which is O(n) on a skewed tree), O(w) for BFS queues, and O(1) only when you are willing to temporarily rewire pointers (Morris). When an interviewer asks "can you do better on space?", that table is the answer.

#DrillPatternTimeSpaceDifficulty
51Inorder TraversalDFS + stackO(n)O(h)Easy
52Preorder TraversalDFS + stackO(n)O(h)Easy
53Maximum Depthpost-order DFSO(n)O(h)Easy
54Same Treepaired recursionO(n)O(h)Easy
55Symmetric Treemirror recursionO(n)O(h)Easy
56Balanced Binary Treepost-order + sentinelO(n)O(h)Easy
57Path Sumtop-down DFSO(n)O(h)Easy
58Diameter of Binary Treepost-order + globalO(n)O(h)Easy
59Level Order TraversalBFSO(n)O(w)Medium
60Zigzag Level OrderBFS + dequeO(n)O(w)Medium
61Lowest Common Ancestorpost-order DFSO(n)O(h)Medium
62Validate BSTtop-down boundsO(n)O(h)Medium
63Construct from Pre + Individe & conquer + mapO(n)O(n)Medium
64Flatten to Linked ListMorris spliceO(n)O(1)Medium
Chapter recap — what to remember
  • Start from the null base case, then decide whether information flows up (return values) or down (parameters).
  • Post-order for height-like answers: depth (53), balanced (56), diameter (58), LCA (61).
  • Top-down state for ancestor context: path sum remainder (57), BST windows (62).
  • Paired recursion for comparing shapes: same tree (54), symmetric (55).
  • BFS with a frozen level size for anything per-level (59, 60).
  • Return one value, record another when the global answer differs from what the parent needs (58), or encode failure as a sentinel (56).
  • Preorder is the serialisation order — it rebuilds trees (63) and defines the flattened order (64).
What to practice next:
  • Extend the templates: Binary Tree Right Side View (BFS), Path Sum II / III (backtracking, prefix sums), Kth Smallest in a BST (inorder), Serialize and Deserialize Binary Tree (preorder + null markers), Binary Tree Maximum Path Sum (Drill 58 with values instead of edges).
  • Theory refreshers: Binary Tree, Binary Search Tree, DFS and BFS.
  • Full single-problem write-ups: LC 94, LC 104, LC 100, LC 101, LC 102, LC 236, LC 98, LC 105; more in the LeetCode trees and BST sets.
  • Next page: 07 Grids & Matrices — the same DFS/BFS templates, applied to a 2-D grid where each cell has four neighbours.