What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

0. Depth-First Search Tree Traversals • Invariant Proof & Speed-Run

Theory Context•Depth-First Search (DFS)

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

Depth-First Search on binary trees is an expression of mathematical induction. A binary tree is not a flat list of nodes—it is a recursive fractal structure where every non-null node is itself the root of two independent, smaller binary trees. Bottom-up divide-and-conquer DFS solves problems by making a "Leap of Faith": assume that your recursive function already works perfectly on the left and right subtrees. Your only responsibility at the current node is to combine those two child answers with the current node's value.

🏟️ The Analogy: Two Auditors Comparing Org Charts

Imagine two auditors, each holding a copy of a company's org chart, tasked with certifying the two charts are identical. Does either auditor read every name on both charts at once? No. Each auditor looks only at the current box on both charts: do the two boxes hold the same title, and are both either empty or both filled? If so, Auditor Left recurses into the left-hand reports on both charts, and Auditor Right recurses into the right-hand reports on both charts. The certification only succeeds if every single delegated comparison, all the way down, also succeeds.

🔑 Why It Works

The elegance of post-order divide-and-conquer is that no node needs to know anything about the global tree structure. By delegating to children and combining their boolean returns with AND, structural and value equality emerges naturally at the root in $O(N)$ time and $O(H)$ stack memory.

Visual Blueprint & State Transition Model

Figure 1 • Depth-First Search (DFS) Core Invariant & State Lifecycle

Core Invariant Specification

Subtree Independence Invariant: Left and right subproblems are disjoint. When a frame returns, the subtree answer is complete and memory is freed.

Boundary Model: Depth-First Recursion / Call Stack Frame Lifecycle

Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.

Loop Invariant Termination

Base case: if not node: return base; recursive calls on left/right child nodes.

The 4 Mental Models of Depth-First Search

Select the recursive return contract and information direction before writing a single line of code.

1Bottom-Up DFS

Leaves ➔ Postorder Child Return ➔ Parent Combine

Postorder DFS (Bottom-Up Recursion)

Spot it when: A node's answer follows from its subtrees' answers: height, balance, counts, lowest common ancestor.

Mode 1 · Bottom-Up DFS

Python

1	from typing import Callable, Optional, TypeVar
2
3	R = TypeVar("R")
4
5	class TreeNode:
6	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
7	self.val = val
8	self.left = left
9	self.right = right
10
11
12	def bottom_up(root: Optional[TreeNode], empty: R, combine: Callable[[TreeNode, R, R], R]) -> R:
13	"""Bottom-Up DFS: the answer for the tree at root, built from the answers of its
14	subtrees.
15	empty is the answer for an empty subtree. combine(node, left, right) builds node's
16	answer from its children's answers.
17	Precondition: a node's answer depends only on the node and on the answers of its two
18	subtrees.
19	Same Tree, Symmetric Tree, Merge Two Binary Trees and Subtree of Another Tree walk
20	two trees at once, so they do not fit.
21	N = number of nodes. H = height. T = the cost of one combine call.
22	Time: O(N * T) \| Space: O(H) recursion stack
23	"""
24	def solve(node: Optional[TreeNode]) -> R:
25	# 1. Base case: the answer for an empty subtree
26	if not node:
27	return empty
28
29	# 2. Divide: solve each subtree on its own
30	left = solve(node.left)
31	right = solve(node.right)
32
33	# 3. Combine: this node's answer comes only from its children's answers
34	return combine(node, left, right)
35
36	return solve(root)

A node's answer depends only on its subtrees' answers, so call maxDepth on root.left and root.right first and combine the two results on the way back up. Each call returns a finished answer for its own subtree, so the parent never looks deeper than those two numbers, and every node is visited exactly once. The trap is the base case: if not root: return 0 must be the value the combine step expects from an empty subtree. A base case that doesn't fit the combine, such as treating a missing child as a leaf in Minimum Depth of Binary Tree (LC 111), returns wrong answers.

Gotchas1 of 4

The trap
Gotcha 1: Taking 1 + min(left_depth, right_depth) with a missing child
Mistake
```
return 1 + min(left_depth, right_depth)
```
Fix
```
if not root.left or not root.right:
    return 1 + max(left_depth, right_depth)
return 1 + min(left_depth, right_depth)
```
What happens: Minimum Depth of Binary Tree (LC 111) counts nodes down to the nearest leaf. A missing child returns 0 from the base case. min then picks that 0, so a node with one child is counted as a leaf. When one child is missing, the depth must come from the other child.
Example: Minimum Depth of Binary Tree (LC 111): root = [2,null,3,null,4,null,5,null,6]
Mistake: returns 1Fix: returns 5
Gotcha 2: Recomputing heights in Balanced Binary Tree (LC 110)
What happens: Balanced Binary Tree (LC 110) needs each subtree's height and whether it is balanced. Calling a separate height function at every node measures the same subtrees again and again. On a balanced tree of n nodes, that costs O(n log n) time instead of O(n). Return both values from one call, for example -1 for an unbalanced subtree.
Gotcha 3: Recursing 10^4 levels deep under Python's default limit
Mistake
```
depth = maxDepth(root)
```
Fix
```
sys.setrecursionlimit(20000)
depth = maxDepth(root)
```
What happens: Each call waits for its children, so the recursion is as deep as the tree. A tree with 10⁴ nodes can be one long chain. Python stops at about 1000 nested calls by default and raises a RecursionError. Raise the limit, or walk the tree with an explicit stack.
Example: root = a chain of 10000 nodes, each the left child of the one before
Mistake: raises RecursionErrorFix: returns 10000
Gotcha 4: Not returning root when it is p or q
Mistake
```
if not root:
```
Fix
```
if not root or root is p or root is q:
```
What happens: In Lowest Common Ancestor of a Binary Tree (LC 236), each call returns the node it found, or None. A call on p or q must return that node itself. When both sides return a node, the current node is the answer. With only if not root, no call ever returns a node, so the answer is None.
Example: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Mistake: returns NoneFix: returns 5

Canonical LeetCode:Maximum Depth of Binary Tree (LC 104)Balanced Binary Tree (LC 110)Lowest Common Ancestor of a Binary Tree (LC 236)Binary Tree Longest Consecutive Sequence (LC 298)Find Leaves of Binary Tree (LC 366)Count Univalue Subtrees (LC 250)Invert Binary Tree (LC 226)Maximum Product of Splitted Binary Tree (LC 1339)Binary Tree Pruning (LC 814)Univalued Binary Tree (LC 965)Count Nodes Equal to Average of Subtree (LC 2265)

Open the Bottom-Up DFS card

2Binary Lifting

Binary Lifting (Kth Ancestor / LCA)

Spot it when: One tree, or any map where each item has exactly one "next" item, and many questions of the form "where do I land after k steps up" (the k-th ancestor, the lowest common ancestor of two nodes, a path between them), with k and the number of questions too large to walk one step at a time.

Mode 2 · Binary Lifting

Python

1	class TreeAncestor:
2	"""Kth Ancestor of a Tree Node: up[j][v] is v's 2^j-th ancestor, so any k is a few
3	jumps.
4	Time: O(N log N) to build, O(log N) per query \| Space: O(N log N)
5	"""
6
7	def __init__(self, n: int, parent: list[int]) -> None:
8	self.LOG = max(1, n.bit_length()) # k <= n, so bits 0..LOG-1 cover every k
9	self.up = [parent[:]] # up[0][v]: v's parent (-1 for the root)
10	for j in range(1, self.LOG):
11	prev = self.up[j - 1]
12	# Two jumps of 2^(j-1) make one jump of 2^j; past the root stays -1
13	self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])
14
15	def getKthAncestor(self, node: int, k: int) -> int:
16	for j in range(self.LOG):
17	if k >> j & 1: # Bit j of k is set: jump 2^j levels up
18	node = self.up[j][node]
19	if node == -1:
20	return -1 # Past the root: stop before up[j][-1] wraps around
21	return node

Store, for every node, where 2^j steps up lands: self.up[0] is the parent list, and each next level is two jumps of the level before, prev[prev[v]]. Then any k is a sum of powers of two, so getKthAncestor jumps once for each set bit of k: node = self.up[j][node] whenever k >> j & 1. This is correct because the jumps add up: 2^j steps followed by 2^j more is exactly 2^(j+1), and the bits of k add up to k, in any order. self.LOG = max(1, n.bit_length()) levels are enough, because k <= n. The trap is the root. A node with fewer than 2^j nodes above it has -1 in level j, and -1 must stay -1: check prev[v] == -1 before reading prev[prev[v]], and return -1 as soon as node == -1. In Python, prev[-1] is not an error but the last node's entry, so an unguarded table quietly turns "no ancestor" into a real node.

Gotchas1 of 5

The trap
Gotcha 1: Reading prev[prev[v]] without checking prev[v] == -1
Mistake
```
self.up.append([prev[prev[v]] for v in range(n)])
```
Fix
```
self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])
```
What happens: -1 means that the node has no ancestor that far up. Python reads prev[-1] as the last entry of the list, not as an error. So an unchecked prev[prev[v]] turns a missing ancestor into a real node. The table then holds wrong jumps.
Example: Kth Ancestor of a Tree Node (LC 1483): n = 7, parent = [-1,0,0,1,1,2,2], getKthAncestor(1, 3)
Mistake: returns 2Fix: returns -1
Gotcha 2: Writing int(math.log2(n)) levels instead of n.bit_length()
Mistake
```
self.LOG = int(math.log2(n))
```
Fix
```
self.LOG = max(1, n.bit_length())
```
What happens: k can be as large as n. On a chain of 8 nodes, k = 8 needs the jump of 2³, which is level 3. int(math.log2(8)) is 3, so the levels are only 0 to 2. The bit for 8 is never tested. The level count comes from the largest k. In Maximize Value of Function in a Ball Passing Game (LC 2836), k reaches 10¹⁰, so use k.bit_length() levels.
Example: n = 8, parent = [-1,0,1,2,3,4,5,6] (a chain), getKthAncestor(7, 8)
Mistake: returns 7Fix: returns -1
Gotcha 3: Filling one node's levels at a time
What happens: Level j of node v reads level j - 1 of another node, prev[v]. When one node's levels are filled at a time, that other node's row may not be built yet. LeetCode does not promise parent[i] < i, so a parent can come later in the list. Build self.up[j] from the whole of self.up[j - 1], one level at a time.
Gotcha 4: Testing k & j instead of k >> j & 1
Mistake
```
if k & j:
```
Fix
```
if k >> j & 1:
```
What happens: k >> j & 1 reads bit j of k. k & j combines k with the level number j itself, bit by bit. For k = 2, k & 1 is 0, so the jump of 2 is skipped. k & 2 is 2 at j = 2, so the code jumps 4 levels instead.
Example: n = 7, parent = [-1,0,0,1,1,2,2], getKthAncestor(5, 2)
Mistake: returns -1Fix: returns 0
Gotcha 5: Jumping again after node becomes -1
Mistake
```
node = self.up[j][node]
```
Fix
```
node = self.up[j][node]
if node == -1:
    return -1
```
What happens: Once node is -1, the walk has passed the root. A later jump reads self.up[j][-1]. Python reads that as the last node's entry, so the walk lands on a real node. Return -1 as soon as node == -1.
Example: n = 8, parent = [-1,0,1,2,3,4,5,6] (a chain), getKthAncestor(1, 6)
Mistake: returns 3Fix: returns -1

Canonical LeetCode:Kth Ancestor of a Tree Node (LC 1483)Minimum Edge Weight Equilibrium Queries in a Tree (LC 2846)Maximize Value of Function in a Ball Passing Game (LC 2836)Number of Ways to Assign Edge Weights II (LC 3559)

Open the Binary Lifting card

3Top-Down DFS

Root ➔ Preorder Argument Passing ➔ Descendant Evaluation

Preorder DFS (Top-Down Recursion)

Spot it when: Whether a node counts depends on the path from the root to it: path sums, 'good' nodes, values compared with ancestors.

Mode 3 · Top-Down DFS

Python

1	from typing import Callable, Optional, TypeVar
2
3	S = TypeVar("S")
4	R = TypeVar("R")
5
6	class TreeNode:
7	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
8	self.val = val
9	self.left = left
10	self.right = right
11
12
13	def top_down(root: Optional[TreeNode], start: S, next_state: Callable[[S, TreeNode], S], visit: Callable[[S, TreeNode], R], combine: Callable[[R, R, R], R], empty: R) -> R:
14	"""Top-Down DFS: combine visit(state, node) over every node, where state describes
15	the path above node.
16	start is the state above the root. next_state(state, node) is the state handed to
17	node's children.
18	combine(here, left, right) joins a node's own result with its subtrees' results, for
19	example a sum or a max.
20	empty is the result of an empty subtree.
21	Precondition: every node is visited, so the template cannot remove nodes from the
22	tree.
23	N = number of nodes. H = height. T = the cost of one next_state, visit or combine
24	call.
25	Time: O(N * T) \| Space: O(H) recursion stack
26	"""
27	def dfs(node: Optional[TreeNode], state: S) -> R:
28	if not node:
29	return empty # Empty subtree: the neutral result
30
31	here = visit(state, node) # Decide with the state passed down
32	child_state = next_state(state, node) # Update the state for the children only
33
34	return combine(here, dfs(node.left, child_state), dfs(node.right, child_state))
35
36	return dfs(root, start)

A node's answer depends on what lies above it, so pass that knowledge down as an argument (max_so_far) instead of searching back up the tree. Each call decides using only its argument and node.val, then hands the updated state (new_max) to both children; because arguments belong to one call, siblings never see each other's changes. Start the state at -inf, so the root counts as good without a special case.

Gotchas1 of 4

The trap
Gotcha 1: Starting max_so_far at 0 instead of -inf
Mistake
```
return dfs(root, 0)
```
Fix
```
return dfs(root, float('-inf'))
```
What happens: The root has no ancestors, so it is always a good node. Node values can be negative. With a start of 0, a negative root fails node.val >= max_so_far, so it is not counted. Starting at -inf, or at root.val, makes the root count.
Example: root = [-1,-2,-3]
Mistake: returns 0Fix: returns 1
Gotcha 2: Keeping the running max in one shared variable
Mistake
```
nonlocal max_so_far
max_so_far = max(max_so_far, node.val)
```
Fix
```
new_max = max(max_so_far, node.val)
```
What happens: With one shared variable, the left subtree raises max_so_far. The raised value is still there when the walk enters the right subtree. So a right-side node is compared with values that are not its ancestors. An argument belongs to one call, so each child sees only its own path.
Example: root = [1,5,2]
Mistake: returns 2Fix: returns 3
Gotcha 3: Checking the sum at an empty child, not a leaf
Mistake
```
if not node:
    return rem == 0
```
Fix
```
if not node:
    return False
if not node.left and not node.right:
    return rem == node.val
```
What happens: Path Sum (LC 112) counts only paths that end at a leaf, a node with no children. A node with one child also has one empty side. A check at the empty side accepts the path that stops at that node. That path does not end at a leaf.
Example: root = [1,2], targetSum = 1
Mistake: returns TrueFix: returns False
Gotcha 4: Adding cur when node is None
Mistake
```
if not node:
    return cur
cur = cur * 10 + node.val
```
Fix
```
if not node:
    return 0
cur = cur * 10 + node.val
if not node.left and not node.right:
    return cur
```
What happens: In Sum Root to Leaf Numbers (LC 129), the state passed down is cur * 10 + node.val. A number is complete only at a leaf. A leaf has two None children, so returning cur at None adds each leaf's number twice. A node with one child also adds its partial number from its None side.
Example: root = [1,2,3]
Mistake: returns 50Fix: returns 25

Canonical LeetCode:Count Good Nodes in Binary Tree (LC 1448)Path Sum (LC 112)Maximum Depth of Binary Tree (LC 104)Binary Tree Longest Consecutive Sequence (LC 298)Sum of Root To Leaf Binary Numbers (LC 1022)Sum Root to Leaf Numbers (LC 129)Maximum Difference Between Node and Ancestor (LC 1026)Sum of Left Leaves (LC 404)Insufficient Nodes in Root to Leaf Paths (LC 1080)

Open the Top-Down DFS card

4Tree Traversals

Tree ➔ Stack Walk (Pre, In or Post) ➔ Nodes In That Order

Tree Traversals (Recursive and Iterative)

Spot it when: The problem names an order for the nodes of a tree (preorder, inorder or postorder), or asks for that order without recursion, or asks for the nodes one at a time like an iterator.

Mode 4 · Tree Traversals

Python

1	from typing import Callable, Literal, Optional
2
3	class TreeNode:
4	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
5	self.val = val
6	self.left = left
7	self.right = right
8
9
10	def traverse(root: Optional[TreeNode], order: Literal["pre", "in", "post"], visit: Callable[[TreeNode], None]) -> None:
11	"""Depth-First Traversal with an explicit stack: visit(node) is called once for
12	every node, in the chosen order.
13	"pre" visits a node before its two subtrees, "in" between them, and "post" after
14	both.
15	Precondition: visit needs only the node itself, and it does not change the tree.
16	N = number of nodes. H = height. T = the cost of one visit call.
17	Time: O(N * T) \| Space: O(H) stack
18	"""
19	# Nodes the walk has pushed and not popped yet; the deepest node is on top
20	stack: list[TreeNode] = []
21	# The node popped most recently; "post" reads it to see that a right subtree is
22	# finished
23	last: Optional[TreeNode] = None
24	node = root
25	while node or stack:
26	# 1. Dive Left:
27	# Push every node on the way down the left edge. "pre" visits each node here,
28	# before both of its subtrees.
29	while node:
30	if order == "pre":
31	visit(node)
32	stack.append(node)
33	node = node.left
34
35	# 2. Finish The Right Subtree First ("post" only):
36	# "post" visits a node after both subtrees. If the right subtree is not
37	# finished, walk it before popping.
38	top = stack[-1]
39	if order == "post" and top.right and top.right is not last:
40	node = top.right
41	continue
42
43	# 3. Pop The Node:
44	# The walk is done with the left subtree, and for "post" with the right subtree
45	# too. "in" and "post" visit the node now. "pre" and "in" then move to the right
46	# subtree.
47	stack.pop()
48	if order != "pre":
49	visit(top)
50	last = top
51	if order != "post":
52	node = top.right

The walk reaches every node three times: on the way down, after the left subtree is finished, and after the right subtree is finished. The order name says which of the three times calls visit. Preorder visits on the way down, inorder after the left subtree, and postorder after the right subtree. So one stack serves all three orders, and only the line that calls visit moves. The inner loop pushes every node on the way down the left edge, so the node that stack.pop() returns has a finished left subtree, and node = node.right walks its right subtree next. Every node is pushed once and popped once, so it is visited once. Postorder is the one order that comes back to a node twice before it leaves, so the template pops a node only when top.right is empty or top.right is last. The trap is where the visit line sits. In inorder, result.append(node.val) goes right after stack.pop(). Next to stack.append(node), it runs on the way down and returns the preorder: [1, 2, 3] instead of [1, 3, 2] on [1,null,2,3].

Gotchas1 of 5

The trap
Gotcha 1: Appending node.val when node is pushed
Mistake
```
while node:
    result.append(node.val)
    stack.append(node)
    node = node.left
node = stack.pop()
```
Fix
```
while node:
    stack.append(node)
    node = node.left
node = stack.pop()
result.append(node.val)
```
What happens: A pushed node has not yet had its left subtree visited. The pushes go from the root down the left edge, so every value is appended before the smaller values that belong in front of it. The list that results is the preorder. On [1,null,2,3], the walk appends 1, then pushes and appends 2, then pushes and appends 3. The result is [1, 2, 3]. The inorder is [1, 3, 2], because 3 is the left child of 2.
Example: Binary Tree Inorder Traversal (LC 94): root = [1,null,2,3]
Mistake: returns [1, 2, 3]Fix: returns [1, 3, 2]
Gotcha 2: Looping while stack instead of while node or stack
Mistake
```
while stack:
```
Fix
```
while node or stack:
```
What happens: stack is empty at the start, and node holds the root. With while stack, the loop body never runs, and the function returns []. The same mistake also appears in the middle of a walk. After the last node on stack is popped, node can still point at a right subtree that has not been walked, while stack is empty.
Example: root = [1,null,2,3]
Mistake: returns []Fix: returns [1, 3, 2]
Gotcha 3: Popping a node in postorder without checking top.right is not last
Mistake
```
if order == "post" and top.right:
```
Fix
```
if order == "post" and top.right and top.right is not last:
```
What happens: In postorder, the walk comes back to a node twice before it leaves it: once from the left subtree and once from the right subtree. top.right is not last tells the two returns apart. Without it, the second return sees top.right again and walks into the right subtree again. On [1,null,2,3], the loop never ends.
Example: root = [1,null,2,3], order = "post"
Mistake: the loop never endsFix: returns [3, 2, 1]
Gotcha 4: Comparing top.right.val with last.val instead of the nodes
Mistake
```
if order == "post" and top.right and (last is None or top.right.val != last.val):
```
Fix
```
if order == "post" and top.right and top.right is not last:
```
What happens: Different nodes can hold the same value. In [1,1,1], the left child (last) and the right child (top.right) both hold 1, so the test decides that the right subtree is finished. The root is popped, and the right child is never visited. The result is [1, 1] instead of [1, 1, 1]. is not compares the nodes themselves.
Example: root = [1,1,1], order = "post"
Mistake: returns [1, 1]Fix: returns [1, 1, 1]
Gotcha 5: Walking a deep tree with recursion
Mistake
```
def walk(node):
    if node:
        walk(node.left)
        result.append(node.val)
        walk(node.right)
```
Fix
```
while node or stack:
    while node:
        stack.append(node)
        node = node.left
    node = stack.pop()
    result.append(node.val)
    node = node.right
```
What happens: Each recursive call waits for the call below it, so the call stack is as deep as the tree is high. Python stops at about 1000 nested calls and raises RecursionError. A chain of 3000 nodes fails. Binary Tree Inorder Traversal (LC 94) has at most 100 nodes, but Binary Search Tree Iterator (LC 173) allows 10^5 nodes, which can form one chain. A list named stack lives on the heap and has no such limit.
Example: root = a chain of 3000 nodes, each the left child of the one before
Mistake: raises RecursionErrorFix: returns 3000

Canonical LeetCode:Binary Tree Inorder Traversal (LC 94)Binary Tree Preorder Traversal (LC 144)Binary Tree Postorder Traversal (LC 145)Binary Search Tree Iterator (LC 173)

Open the Tree Traversals card

Built on the mental models above

Construct Binary TreeTree Construction (Build from Preorder + Inorder)
The recursion works on index ranges of the two traversals, and the next preorder value is the root of each range.
Tree Diameter DPTree DP (Max Path Sum / Diameter)
The function returns one downward leg, and a separate global_max records the best path that bends at each node.
Two Tree WalkTwo-Tree DFS (Walking a Pair of Nodes Together)
The call takes a pair of nodes, one from each tree, and combines the pair with the answers of its two child pairs.
Tree State DPTree State DP (Return Several States per Node)
Each call returns one best value per state of the node, such as taken and skipped, so the parent never looks at grandchildren.
RerootRerooting a Tree (Answer for Every Root)
A second pass walks down and hands each child the answer for everything outside its subtree, so every node gets the answer as if it were the root.
Tree As StringTree as a String (Serialize and Canonical Key)
Each call returns a string built from its children's strings, so equal subtrees give equal strings that can be counted or compared.
Rewire TreeRewire Tree (Return the Node That Stays)
Each call returns the node that stays in its place, which may be None, and the parent stores that return value as its child.
Greedy Tree DPGreedy Postorder Tree DP (Distribute Coins, Minimum Fuel Cost)
Each subtree returns one signed number, what it holds minus what it needs, and the parent counts that many crossings of the edge above it.
BST BoundsBST Property / Range Validation
The value passed down is a pair (low, high), and the BST rule picks the single branch to follow.
Root-to-Leaf PathsRoot-to-Leaf Path Backtracking
The path above is a shared list: append before the recursive calls, pop after them, and copy it at a leaf.
BST InorderInorder Traversal as a Sorted Stream (Kth Smallest in BST, BST Iterator)
An inorder walk visits a BST in ascending order, so it can stop as soon as it has the value it needs.

The DFS Decision Rule

When facing an unseen binary tree or recursive graph problem, ask these questions in order:

Step 1.Does the problem optimize an arbitrary path that can bend/turn at any node (diameter, maximum path sum)?

➔ Tree Diameter DP

Binary Tree Maximum Path Sum (LC 124)Diameter of Binary Tree (LC 543)

Update global maximum with 2-legged summit (node.val + left + right); return strictly 1-legged branch (node.val + max(left, right)) upward.

Step 2.Is each node a choice (take it or not, covered or not) tied to its children's choices, so one number per subtree can't say which choice its root made?

➔ Tree State DP

House Robber III (LC 337)Binary Tree Cameras (LC 968)

Return one best total per state of the node, e.g. (rob, skip), and combine the children's tuples in the parent.

Step 3.Is the problem a greedy tree-covering decision driven by each child's status (e.g. minimum cameras, moving coin surplus/deficit)?

➔ Greedy Tree DP

Distribute Coins in Binary Tree (LC 979)Minimum Fuel Cost to Report to the Capital (LC 2477)

Bubble each child's status or surplus up from the postorder call; the parent acts only when a child needs it and counts what crosses each edge.

Step 4.Is the input a Binary Search Tree (BST) that you validate, search, insert into, delete from or trim?

➔ BST Bounds

Validate Binary Search Tree (LC 98)Lowest Common Ancestor of a Binary Search Tree (LC 235)

Propagate open intervals (low, high) downward or steer recursion down a single branch based on directional comparison.

Step 5.Does the problem list the nodes of a tree in a named order (preorder, inorder or postorder), or ask for that order without recursion?

➔ Tree Traversals

Binary Tree Inorder Traversal (LC 94)Binary Tree Preorder Traversal (LC 144)

Walk with an explicit stack and change only the line that calls visit: on the way down for preorder, after the left subtree for inorder, after the right subtree for postorder.

Step 6.Is the input a BST and the answer depends on its values in sorted order (k-th smallest, gaps between neighbours, an iterator)?

➔ BST Inorder

Kth Smallest Element in a BST (LC 230)Minimum Absolute Difference in BST (LC 530)

Walk inorder (left, node, right), iteratively with a stack when you must stop early, and count on the pop.

Step 7.Does the problem require reconstructing full root-to-leaf paths?

➔ Root-to-Leaf Paths

Path Sum II (LC 113)Binary Tree Paths (LC 257)

Mutate a single shared buffer on entry (append), snapshot deep copies at true leaves (list(path)), and pop on exit to restore state for sibling branches.

Step 8.Does evaluating the current node require knowing ancestral context (e.g. running maximum, path prefix sum)?

➔ Top-Down DFS

Count Good Nodes in Binary Tree (LC 1448)Path Sum (LC 112)

Pass accumulated constraints downward via arguments: dfs(child, max(ancestor_max, node.val)).

Step 9.Does the problem give you two trees, or one tree compared with itself, and ask whether they match, mirror each other or merge, so each answer pairs a node of one tree with a node of the other?

➔ Two Tree Walk

Same Tree (LC 100)Symmetric Tree (LC 101)

Call the recursion on a pair of nodes, one from each tree: pair p.left with q.left (or with q.right for a mirror), return p is None and q is None when a node is missing, and combine the pair with its two child pairs' answers.

Step 10.Does the problem compare the subtrees of one tree with each other (which shapes repeat, or whether one tree appears inside another), or ask for a text form of a tree?

➔ Tree As String

Find Duplicate Subtrees (LC 652)Serialize and Deserialize Binary Tree (LC 297)

Return a string from every call, built from the node value and the strings of its two children, with a marker for a missing child: equal subtrees give equal strings, so count or compare the strings.

Step 11.Does the problem ask for a deleted, pruned or rewired tree: remove some nodes and return the roots that remain, or cut leaves that match a rule?

➔ Rewire Tree

Delete Nodes And Return Forest (LC 1110)Binary Tree Pruning (LC 814)

Return from every call the node that should stay in its place, or None: set node.left = rewire(node.left) and node.right = rewire(node.right) first, then decide whether this node stays.

Step 12.Does the problem ask for an answer for every node as if that node were the root (the sum of distances from each node, the cost to reach all nodes from each start)?

➔ Reroot

Sum of Distances in Tree (LC 834)Count Number of Possible Root Nodes (LC 2581)

Run one pass up the tree to get each subtree's counts and sums, then one pass down that hands each child the answer for everything outside its subtree.

Step 13.Does the problem ask for an aggregate property or structural transform of the whole tree (depth, height, balance, invert, or LCA)?

➔ Bottom-Up DFS

Maximum Depth of Binary Tree (LC 104)Balanced Binary Tree (LC 110)

Recursively solve left and right subtrees independently; synthesize answers upon return: return combine(node.val, dfs(left), dfs(right)).

Step 14.Do you get two traversal orders of one tree with distinct values and must rebuild it?

➔ Construct Binary Tree

Construct Binary Tree from Preorder and Inorder Traversal (LC 105)Construct Binary Tree from Inorder and Postorder Traversal (LC 106)

The first preorder value is the root; its index in inorder (from a value-to-index map) splits the left and right subtrees; recurse on each.

Step 15.Are there many 'where do I land after k steps up' questions (k-th ancestor, LCA), with k and the query count too large to walk one step at a time?

➔ Binary Lifting

Kth Ancestor of a Tree Node (LC 1483)Minimum Edge Weight Equilibrium Queries in a Tree (LC 2846)

Precompute up[j][v] = up[j-1][up[j-1][v]], then answer a jump of k with the 2^j jumps of k's set bits.

Pattern Architecture & Invariant Design Masterclass

Depth-First Search on trees operates on a foundational principle: Subtree Divide and Conquer. From any node in a tree, the entire problem decomposes into identical, smaller subproblems on its left and right subtrees.

Because trees are connected acyclic graphs with exactly one path between any two nodes, a parent node can solve its own problem simply by synthesizing the already-solved answers of its children.

Code / Blueprint

       [ Parent Node ]
          /        \
   (left_res)    (right_res)
      /              \
[ Left Subtree ]   [ Right Subtree ]
 (Solved fully)     (Solved fully)

The breakthrough mental model for mastering Tree DFS is the Recursive Leap of Faith, and most tree DFS frames follow this 3-step cycle:

🛑 The Floor — Base Case Check (if not node: return base_val): When node is None or a leaf is reached, return the mathematical identity element (e.g. 0 for depth, None for trees, True for validity). This anchors the recursion — without it, the call stack recurses infinitely.
🌿 The Leap of Faith — Divide & Recurse (left = dfs(node.left), right = dfs(node.right)): Trust that dfs(node.left) and dfs(node.right) return 100% correct, complete solutions for their respective subtrees. Do not trace the recursion in your head. Left and right subtrees have zero shared state (Subtree Independence Invariant).
💎 The Synthesis — Combine & Bubble Up (return combine(node.val, left, right)): Write only the combine logic that builds the parent's answer from node.val, left_res, and right_res, then return that value upward. When this frame returns, its subtree is fully resolved and its stack memory is immediately freed.

The 3-Step Recursive Frame Lifecycle

Interactive Architecture Diagram

Synthesizing vector architecture diagram...

Variable Anatomy: The 7 Variables Every Tree DFS Uses

Code / Blueprint

def dfs(node: Optional[TreeNode], min_val: float, max_val: float, path: list[int]) -> int:
    if not node:
        return 0                                    # 1. base_val (Recursion floor)
    
    path.append(node.val)                           # 2. path (Current branch accumulator)
    left_res = dfs(node.left, min_val, node.val, path)   # 3. left_res (Left subtree answer)
    right_res = dfs(node.right, node.val, max_val, path) # 4. right_res (Right subtree answer)
    path.pop()                                      # 5. un-choose (Backtrack step)
    
    return max(left_res, right_res) + 1             # 6. combine (Bubble-up synthesis)

Variable	Type / Role	Purpose in Tree DFS	Failure Mode if Missing / Mismanaged
`node`	`Optional[TreeNode]`	Pointer to current tree node being evaluated in active call frame.	Infinite recursion if `node.left` / `node.right` not advanced.
`base_val`	`int / bool / None`	Neutral mathematical identity returned when hitting empty branch (`None`).	Returning wrong base (e.g. `1` instead of `0`) shifts depth off-by-one.
`left_res`	`Any (int, bool, Node)`	Fully solved result returned by left subtree recursive call.	Tracing recursion manually leads to cognitive overload.
`right_res`	`Any (int, bool, Node)`	Fully solved result returned by right subtree recursive call.	Must be treated symmetrically or pruned in BSTs.
`low` / `high`	`float / int`	Top-down inherited bounds passed downwards to validate search space.	Checking only immediate child `left < node < right` misses deep BST violations.
`path`	`list[int]`	Shared mutable buffer tracking active root-to-leaf path.	Appending `path` directly without `list(path)` copies mutates recorded results.
`global_max`	`list[int]` / `nonlocal`	Global accumulator tracking cross-subtree values (e.g. Tree Diameter, Max Path Sum).	Returning local branch sum while neglecting bending path across root.

The 3 Dimensions of Tree DFS

Every Tree DFS problem can be classified across 3 orthogonal dimensions:

Code / Blueprint

                      DIMENSION 1: INFORMATION FLOW
               ┌───────────────────────┴───────────────────────┐
               ▼                                               ▼
     Bottom-Up Synthesis                              Top-Down Accumulation
   (Post-Order Return Values)                      (Pre-Order Parameter Passing)
   e.g. Max Depth, Balanced Tree                   e.g. Valid BST, Good Nodes
 
                      DIMENSION 2: TRAVERSAL ORDER
       ┌───────────────────────┼───────────────────────┐
       ▼                       ▼                       ▼
   Pre-Order               In-Order                Post-Order
 (Root → L → R)          (L → Root → R)          (L → R → Root)
 Path Accumulation       BST Monotonic Sort      Subtree Synthesis
 
                   DIMENSION 3: CALL-STACK BOUND O(H)
               ┌───────────────────────┴───────────────────────┐
               ▼                                               ▼
         Balanced Tree                                   Skewed Chain
        H = O(log N)                                      H = O(N)

Dimension 1: Information Direction (Bottom-Up vs Top-Down):
- Bottom-Up: Parent answers depend on child answers. Recurse first, combine on return (Post-Order).
- Top-Down: Child validity depends on ancestor constraints. Pass running bounds downward in arguments (Pre-Order).
Dimension 2: Traversal Order (Pre vs In vs Post):
- Pre-Order (Root → Left → Right): Work happens before recursion (path building, serialization).
- In-Order (Left → Root → Right): Work happens between children. On BSTs, yields strictly sorted ascending values.
- Post-Order (Left → Right → Root): Work happens after recursion (height calculations, subtree deletion, inversion).
Dimension 3: Call-Stack Memory Bound ( $O(H)$ ):
- Auxiliary memory is strictly bounded by tree height $H$ .
- Balanced Tree: $H = O(\log N)$ stack frames.
- Degenerate Skewed Chain: $H = O(N)$ stack frames (can cause recursion depth overflow).

The 5 Master Tree DFS Paradigms

Code / Blueprint

┌─────────────────────────────────────────────────────────────────────────────┐
│                       THE 5 MASTER TREE DFS PARADIGMS                       │
├────────────────────────────────┬────────────────────────────────────────────┤
│ 1. Pure Divide & Conquer       │ Bottom-up return bubbling: LC 104, 110, 236│
│ 2. In-Place Tree Mutation      │ Post-order subtree swapping: LC 226, 114   │
│ 3. Top-Down Parameter Passing  │ Ancestor constraint propagation: LC 1448   │
│ 4. BST Monotonic / Split       │ Exploiting sorted order & bounds: LC 98,235│
│ 5. Tree Backtracking (Paths)   │ Mutable buffer choose-explore-unchoose: 113│
└────────────────────────────────┴────────────────────────────────────────────┘

Understanding Invariants: Subtree Independence & Memory Bound

Subtree Independence Invariant: Left and right subtrees are completely disjoint with zero shared mutable state. When a recursive call frame returns, its subtree answer is mathematically complete, and its stack memory is immediately reclaimed.

Depth-First Search explores branches to maximal depth before backtracking. The call stack maintains the active ancestor chain, allowing base cases to anchor the recursion and parent nodes to synthesize optimal answers bottom-up without global coordination.

Base Floor Anchor & Out-of-Bounds Pruning

Condition: If node is None

Action: return neutral algebraic base identity (0 for depth/count, None for tree pointers, True for validity) immediately

Terminates recursive descent at leaf boundaries without creating non-existent child frames, maintaining O(N) total calls.

Monotonic Range & Branch Elimination Pruning

Condition: In a BST: target < node.val (pruning right) or target > node.val (pruning left); or ancestor bounds violation: not (low < node.val < high)

Action: Prune the infeasible child branch immediately; do not dispatch recursive call

Spatial monotonicity guarantees target values cannot exist in the pruned branch, reducing time complexity from O(N) full traversal to O(H) single-path search.

Common Questions

"When my code calls dfs(root.left) and then dfs(root.right), how should I picture what's happening — does the current node handle both sides at the same time, or does execution go all the way down the left side first, come back up, and only then start the right side?"

You need both mental models — you just use them at different times.
- While you are designing the algorithm, use the Delegation mindset: at the current node, you explore both left and right.
- While you are tracing or debugging a program, use the Stack mindset: the machine goes all the way down the left branch, pops all the way back up, and only then goes down the right branch.
1. The Design mindset — think locally (Delegation). Writing a recursive function while trying to visualize the entire call stack diving down and popping back up will overwhelm your working memory. Instead, treat dfs as a subcontractor: you are standing at the current node, and you say "I need the answer for my left side — go figure that out and hand it back to me," then "I need the answer for my right side — go get that too." This is exactly the Recursive Leap of Faith from the mental model above: you trust that dfs(node.left) and dfs(node.right) each return a complete, correct answer, and you never trace how they got there. You only care about what comes back to the current frame. This is what makes designing Tree DP tractable — you focus on one question: "What information do I pass down to my children, and what information do I need them to pass back up to me?"

2. The Debug mindset — think procedurally (Stack). When your code is failing, or you're reading someone else's recursive solution (like a Tree DP zigzag-path walk), switch to the computer's actual execution order. The computer cannot do two things at once: when it hits dfs(node.left), it fully suspends the current frame and dives all the way down the left subtree, hitting leaf after leaf until it returns None/base case. Only after the entire left subtree has finished and popped off the call stack does execution return to the current frame and finally start dfs(node.right).

The takeaway: when you're staring at a blank editor trying to solve a tree problem, don't try to picture the execution diving down and popping back up — that mindset is for verifying code, not writing it. Stay in the Delegation mindset: focus on one single node, and ask what it needs from its children and what it owes its parent.
"In problems like Binary Tree Maximum Path Sum, why do we need both a global_max variable AND a return value from dfs — isn't the return value enough?"

Because they answer two different questions, and a parent can only make use of one of them.

The return value answers "what is the best score my parent can extend a path through, using just me and one of my children?" A path can only continue upward through a single leg — a parent can't accept a path that already bent at you and also keep extending it, because a path can't fork twice. That's why the return is node.val + max(left_gain, right_gain): exactly one leg, chosen greedily.

global_max answers a completely different question: "what is the best score of any path that is allowed to bend at this exact node, using both legs at once?" That path can never be extended further — it already used both directions — so it can only ever update a running best-so-far, never be returned upward.

Every node computes both from the same two recursive calls: global_max = max(global_max, node.val + left_gain + right_gain) (the two-legged "summit," compared against the global best) and return node.val + max(left_gain, right_gain) (the single-legged branch, handed to the parent). Conflating the two — returning the two-legged value, or forgetting to update the global with it — is the single most common bug in this archetype. max(..., 0) on each leg is the other half: a path is always allowed to decline a negative subtree rather than drag the total down.

Coach discussion points

1.
"Your recursive function uses no explicit data structures. Why is its space complexity not $O(1)$ ?" $\to$ Call-stack frames consume $O(H)$ auxiliary RAM ( $O(N)$ on skewed trees).
2.
"Why must BST validation pass ranges downward rather than checking left and right children locally?" $\to$ Subtree validity is a global invariant across all ancestors.
3.
"When does a problem require post-order vs pre-order traversal?" $\to$ Post-order when parent needs child results; pre-order when child needs ancestor context.

Complexity analysis

Metric	Balanced Tree	Skewed Chain Tree	Derivation / Mechanism
Time Complexity	$O(N)$	$O(N)$	Every node is entered once and left once; work per frame is $O(1)$ .
Auxiliary Space	$O(\log N)$	$O(N)$	Memory bounded strictly by call stack frame depth (tree height $H$ ).
Path Copying (LC 113)	$O(N \log N)$	$O(N)$	Snapshotting `list(path)` at $K$ matching leaves costs $O(H)$ per match, $O(N \cdot H)$ in all. A chain has one leaf, so one copy. The $O(N^2)$ worst case is a caterpillar: about $N/2$ leaves, up to $N/2$ deep (4000 nodes copy 2,003,000 values).

Production Systems Deployment & Motivation

A file system needs to report the total size of a folder. It cannot know its own size without first knowing the sizes of every subfolder — so it descends into the first subfolder, which descends into its first subfolder, all the way down to a folder that contains only files. That one answers immediately. Its answer flows back up to its parent, which adds it to its siblings' answers, and so on until the top-level folder has a number. du -sh, dependency resolvers, and JSON serialisers all do exactly this.

Mastery Roadmap & Prerequisite Graph

💡 Don't worry if recursive leap-of-faith thinking feels daunting right now! DFS decomposes trees and graphs into disjoint subproblems solved cleanly by the call stack. As you progress through the Archetype Variants (from Tree Max Path Sum and Lowest Common Ancestor to Number of Islands and Topological Cycle Checks), each hands-on challenge will cement this intuition until combining dfs(child) returns and unwinding recursion becomes second nature.

Base case floor error: Returning 1 instead of 0 when node is None. An empty tree has depth 0, while a leaf node has depth 1. Returning 1 shifts every path depth by +1.
Skewed tree call-stack overflow: In degenerate linked-list trees ( $O(N)$ height), deep recursion triggers stack overflow. Production systems require iterative stack traversal (stack = [(root, 1)]).
Node count vs edge count ambiguity: LeetCode defines depth as the number of nodes along the path (root alone = 1). Graph theory often counts edges (root alone = 0). Always clarify unit definitions.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "explore all paths", "tree traversal / branch evaluation", "connected components / reachability", "topological sort on DAG(Directed Acyclic Graph)". Deep exhaustive exploration along a path before backtracking to explore alternate branches.

CONSTRAINTS & BOUNDS

Graph or tree with $V$ vertices and $E$ edges. Time budget is $O(V + E)$ when visited states are memoized or marked. Call stack depth is bounded by tree height $O(H)$ or graph path length $O(V)$ ; recursion exceeding $10^4$ frames risks call stack overflow.

FAANG PRODUCTION TRAPS & EDGE CASES

Call stack overflow (stack overflow exception) on deep or degenerate linear graphs ( $N > 10^4$ ); infinite recursion loops on cyclic graphs without a visited set; modifying shared state without restoring it on backtracks.

Theory Context•Depth-First Search (DFS)

Conceptual Foundation & Intuitive Analogy

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: Two Auditors Comparing Org Charts

🔑 Why It Works

Visual Blueprint & State Transition Model

Figure 1 • Depth-First Search (DFS) Core Invariant & State Lifecycle

Core Invariant Specification

Subtree Independence Invariant: Left and right subproblems are disjoint. When a frame returns, the subtree answer is complete and memory is freed.

Boundary Model: Depth-First Recursion / Call Stack Frame Lifecycle

Subtree bottom-up aggregation: a node combines child subtree solutions upon backtrack; top-down invariants pass accumulated state down the path.

Loop Invariant Termination

Base case: if not node: return base; recursive calls on left/right child nodes.

The 4 Mental Models of Depth-First Search

Select the recursive return contract and information direction before writing a single line of code.

1Bottom-Up DFS

Leaves ➔ Postorder Child Return ➔ Parent Combine

Postorder DFS (Bottom-Up Recursion)

Spot it when: A node's answer follows from its subtrees' answers: height, balance, counts, lowest common ancestor.

Mode 1 · Bottom-Up DFS

Python

1	from typing import Callable, Optional, TypeVar
2
3	R = TypeVar("R")
4
5	class TreeNode:
6	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
7	self.val = val
8	self.left = left
9	self.right = right
10
11
12	def bottom_up(root: Optional[TreeNode], empty: R, combine: Callable[[TreeNode, R, R], R]) -> R:
13	"""Bottom-Up DFS: the answer for the tree at root, built from the answers of its
14	subtrees.
15	empty is the answer for an empty subtree. combine(node, left, right) builds node's
16	answer from its children's answers.
17	Precondition: a node's answer depends only on the node and on the answers of its two
18	subtrees.
19	Same Tree, Symmetric Tree, Merge Two Binary Trees and Subtree of Another Tree walk
20	two trees at once, so they do not fit.
21	N = number of nodes. H = height. T = the cost of one combine call.
22	Time: O(N * T) \| Space: O(H) recursion stack
23	"""
24	def solve(node: Optional[TreeNode]) -> R:
25	# 1. Base case: the answer for an empty subtree
26	if not node:
27	return empty
28
29	# 2. Divide: solve each subtree on its own
30	left = solve(node.left)
31	right = solve(node.right)
32
33	# 3. Combine: this node's answer comes only from its children's answers
34	return combine(node, left, right)
35
36	return solve(root)

Gotchas1 of 4

The trap
Gotcha 1: Taking 1 + min(left_depth, right_depth) with a missing child
Mistake
```
return 1 + min(left_depth, right_depth)
```
Fix
```
if not root.left or not root.right:
    return 1 + max(left_depth, right_depth)
return 1 + min(left_depth, right_depth)
```
What happens: Minimum Depth of Binary Tree (LC 111) counts nodes down to the nearest leaf. A missing child returns 0 from the base case. min then picks that 0, so a node with one child is counted as a leaf. When one child is missing, the depth must come from the other child.
Example: Minimum Depth of Binary Tree (LC 111): root = [2,null,3,null,4,null,5,null,6]
Mistake: returns 1Fix: returns 5
Gotcha 2: Recomputing heights in Balanced Binary Tree (LC 110)
What happens: Balanced Binary Tree (LC 110) needs each subtree's height and whether it is balanced. Calling a separate height function at every node measures the same subtrees again and again. On a balanced tree of n nodes, that costs O(n log n) time instead of O(n). Return both values from one call, for example -1 for an unbalanced subtree.
Gotcha 3: Recursing 10^4 levels deep under Python's default limit
Mistake
```
depth = maxDepth(root)
```
Fix
```
sys.setrecursionlimit(20000)
depth = maxDepth(root)
```
What happens: Each call waits for its children, so the recursion is as deep as the tree. A tree with 10⁴ nodes can be one long chain. Python stops at about 1000 nested calls by default and raises a RecursionError. Raise the limit, or walk the tree with an explicit stack.
Example: root = a chain of 10000 nodes, each the left child of the one before
Mistake: raises RecursionErrorFix: returns 10000
Gotcha 4: Not returning root when it is p or q
Mistake
```
if not root:
```
Fix
```
if not root or root is p or root is q:
```
What happens: In Lowest Common Ancestor of a Binary Tree (LC 236), each call returns the node it found, or None. A call on p or q must return that node itself. When both sides return a node, the current node is the answer. With only if not root, no call ever returns a node, so the answer is None.
Example: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Mistake: returns NoneFix: returns 5

Open the Bottom-Up DFS card

2Binary Lifting

Binary Lifting (Kth Ancestor / LCA)

Mode 2 · Binary Lifting

Python

1	class TreeAncestor:
2	"""Kth Ancestor of a Tree Node: up[j][v] is v's 2^j-th ancestor, so any k is a few
3	jumps.
4	Time: O(N log N) to build, O(log N) per query \| Space: O(N log N)
5	"""
6
7	def __init__(self, n: int, parent: list[int]) -> None:
8	self.LOG = max(1, n.bit_length()) # k <= n, so bits 0..LOG-1 cover every k
9	self.up = [parent[:]] # up[0][v]: v's parent (-1 for the root)
10	for j in range(1, self.LOG):
11	prev = self.up[j - 1]
12	# Two jumps of 2^(j-1) make one jump of 2^j; past the root stays -1
13	self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])
14
15	def getKthAncestor(self, node: int, k: int) -> int:
16	for j in range(self.LOG):
17	if k >> j & 1: # Bit j of k is set: jump 2^j levels up
18	node = self.up[j][node]
19	if node == -1:
20	return -1 # Past the root: stop before up[j][-1] wraps around
21	return node

Gotchas1 of 5

The trap
Gotcha 1: Reading prev[prev[v]] without checking prev[v] == -1
Mistake
```
self.up.append([prev[prev[v]] for v in range(n)])
```
Fix
```
self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)])
```
What happens: -1 means that the node has no ancestor that far up. Python reads prev[-1] as the last entry of the list, not as an error. So an unchecked prev[prev[v]] turns a missing ancestor into a real node. The table then holds wrong jumps.
Example: Kth Ancestor of a Tree Node (LC 1483): n = 7, parent = [-1,0,0,1,1,2,2], getKthAncestor(1, 3)
Mistake: returns 2Fix: returns -1
Gotcha 2: Writing int(math.log2(n)) levels instead of n.bit_length()
Mistake
```
self.LOG = int(math.log2(n))
```
Fix
```
self.LOG = max(1, n.bit_length())
```
What happens: k can be as large as n. On a chain of 8 nodes, k = 8 needs the jump of 2³, which is level 3. int(math.log2(8)) is 3, so the levels are only 0 to 2. The bit for 8 is never tested. The level count comes from the largest k. In Maximize Value of Function in a Ball Passing Game (LC 2836), k reaches 10¹⁰, so use k.bit_length() levels.
Example: n = 8, parent = [-1,0,1,2,3,4,5,6] (a chain), getKthAncestor(7, 8)
Mistake: returns 7Fix: returns -1
Gotcha 3: Filling one node's levels at a time
What happens: Level j of node v reads level j - 1 of another node, prev[v]. When one node's levels are filled at a time, that other node's row may not be built yet. LeetCode does not promise parent[i] < i, so a parent can come later in the list. Build self.up[j] from the whole of self.up[j - 1], one level at a time.
Gotcha 4: Testing k & j instead of k >> j & 1
Mistake
```
if k & j:
```
Fix
```
if k >> j & 1:
```
What happens: k >> j & 1 reads bit j of k. k & j combines k with the level number j itself, bit by bit. For k = 2, k & 1 is 0, so the jump of 2 is skipped. k & 2 is 2 at j = 2, so the code jumps 4 levels instead.
Example: n = 7, parent = [-1,0,0,1,1,2,2], getKthAncestor(5, 2)
Mistake: returns -1Fix: returns 0
Gotcha 5: Jumping again after node becomes -1
Mistake
```
node = self.up[j][node]
```
Fix
```
node = self.up[j][node]
if node == -1:
    return -1
```
What happens: Once node is -1, the walk has passed the root. A later jump reads self.up[j][-1]. Python reads that as the last node's entry, so the walk lands on a real node. Return -1 as soon as node == -1.
Example: n = 8, parent = [-1,0,1,2,3,4,5,6] (a chain), getKthAncestor(1, 6)
Mistake: returns 3Fix: returns -1

Open the Binary Lifting card

3Top-Down DFS

Root ➔ Preorder Argument Passing ➔ Descendant Evaluation

Preorder DFS (Top-Down Recursion)

Spot it when: Whether a node counts depends on the path from the root to it: path sums, 'good' nodes, values compared with ancestors.

Mode 3 · Top-Down DFS

Python

1	from typing import Callable, Optional, TypeVar
2
3	S = TypeVar("S")
4	R = TypeVar("R")
5
6	class TreeNode:
7	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
8	self.val = val
9	self.left = left
10	self.right = right
11
12
13	def top_down(root: Optional[TreeNode], start: S, next_state: Callable[[S, TreeNode], S], visit: Callable[[S, TreeNode], R], combine: Callable[[R, R, R], R], empty: R) -> R:
14	"""Top-Down DFS: combine visit(state, node) over every node, where state describes
15	the path above node.
16	start is the state above the root. next_state(state, node) is the state handed to
17	node's children.
18	combine(here, left, right) joins a node's own result with its subtrees' results, for
19	example a sum or a max.
20	empty is the result of an empty subtree.
21	Precondition: every node is visited, so the template cannot remove nodes from the
22	tree.
23	N = number of nodes. H = height. T = the cost of one next_state, visit or combine
24	call.
25	Time: O(N * T) \| Space: O(H) recursion stack
26	"""
27	def dfs(node: Optional[TreeNode], state: S) -> R:
28	if not node:
29	return empty # Empty subtree: the neutral result
30
31	here = visit(state, node) # Decide with the state passed down
32	child_state = next_state(state, node) # Update the state for the children only
33
34	return combine(here, dfs(node.left, child_state), dfs(node.right, child_state))
35
36	return dfs(root, start)

Gotchas1 of 4

The trap
Gotcha 1: Starting max_so_far at 0 instead of -inf
Mistake
```
return dfs(root, 0)
```
Fix
```
return dfs(root, float('-inf'))
```
What happens: The root has no ancestors, so it is always a good node. Node values can be negative. With a start of 0, a negative root fails node.val >= max_so_far, so it is not counted. Starting at -inf, or at root.val, makes the root count.
Example: root = [-1,-2,-3]
Mistake: returns 0Fix: returns 1
Gotcha 2: Keeping the running max in one shared variable
Mistake
```
nonlocal max_so_far
max_so_far = max(max_so_far, node.val)
```
Fix
```
new_max = max(max_so_far, node.val)
```
What happens: With one shared variable, the left subtree raises max_so_far. The raised value is still there when the walk enters the right subtree. So a right-side node is compared with values that are not its ancestors. An argument belongs to one call, so each child sees only its own path.
Example: root = [1,5,2]
Mistake: returns 2Fix: returns 3
Gotcha 3: Checking the sum at an empty child, not a leaf
Mistake
```
if not node:
    return rem == 0
```
Fix
```
if not node:
    return False
if not node.left and not node.right:
    return rem == node.val
```
What happens: Path Sum (LC 112) counts only paths that end at a leaf, a node with no children. A node with one child also has one empty side. A check at the empty side accepts the path that stops at that node. That path does not end at a leaf.
Example: root = [1,2], targetSum = 1
Mistake: returns TrueFix: returns False
Gotcha 4: Adding cur when node is None
Mistake
```
if not node:
    return cur
cur = cur * 10 + node.val
```
Fix
```
if not node:
    return 0
cur = cur * 10 + node.val
if not node.left and not node.right:
    return cur
```
What happens: In Sum Root to Leaf Numbers (LC 129), the state passed down is cur * 10 + node.val. A number is complete only at a leaf. A leaf has two None children, so returning cur at None adds each leaf's number twice. A node with one child also adds its partial number from its None side.
Example: root = [1,2,3]
Mistake: returns 50Fix: returns 25

Open the Top-Down DFS card

4Tree Traversals

Tree ➔ Stack Walk (Pre, In or Post) ➔ Nodes In That Order

Tree Traversals (Recursive and Iterative)

Spot it when: The problem names an order for the nodes of a tree (preorder, inorder or postorder), or asks for that order without recursion, or asks for the nodes one at a time like an iterator.

Mode 4 · Tree Traversals

Python

1	from typing import Callable, Literal, Optional
2
3	class TreeNode:
4	def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
5	self.val = val
6	self.left = left
7	self.right = right
8
9
10	def traverse(root: Optional[TreeNode], order: Literal["pre", "in", "post"], visit: Callable[[TreeNode], None]) -> None:
11	"""Depth-First Traversal with an explicit stack: visit(node) is called once for
12	every node, in the chosen order.
13	"pre" visits a node before its two subtrees, "in" between them, and "post" after
14	both.
15	Precondition: visit needs only the node itself, and it does not change the tree.
16	N = number of nodes. H = height. T = the cost of one visit call.
17	Time: O(N * T) \| Space: O(H) stack
18	"""
19	# Nodes the walk has pushed and not popped yet; the deepest node is on top
20	stack: list[TreeNode] = []
21	# The node popped most recently; "post" reads it to see that a right subtree is
22	# finished
23	last: Optional[TreeNode] = None
24	node = root
25	while node or stack:
26	# 1. Dive Left:
27	# Push every node on the way down the left edge. "pre" visits each node here,
28	# before both of its subtrees.
29	while node:
30	if order == "pre":
31	visit(node)
32	stack.append(node)
33	node = node.left
34
35	# 2. Finish The Right Subtree First ("post" only):
36	# "post" visits a node after both subtrees. If the right subtree is not
37	# finished, walk it before popping.
38	top = stack[-1]
39	if order == "post" and top.right and top.right is not last:
40	node = top.right
41	continue
42
43	# 3. Pop The Node:
44	# The walk is done with the left subtree, and for "post" with the right subtree
45	# too. "in" and "post" visit the node now. "pre" and "in" then move to the right
46	# subtree.
47	stack.pop()
48	if order != "pre":
49	visit(top)
50	last = top
51	if order != "post":
52	node = top.right

Gotchas1 of 5

The trap
Gotcha 1: Appending node.val when node is pushed
Mistake
```
while node:
    result.append(node.val)
    stack.append(node)
    node = node.left
node = stack.pop()
```
Fix
```
while node:
    stack.append(node)
    node = node.left
node = stack.pop()
result.append(node.val)
```
What happens: A pushed node has not yet had its left subtree visited. The pushes go from the root down the left edge, so every value is appended before the smaller values that belong in front of it. The list that results is the preorder. On [1,null,2,3], the walk appends 1, then pushes and appends 2, then pushes and appends 3. The result is [1, 2, 3]. The inorder is [1, 3, 2], because 3 is the left child of 2.
Example: Binary Tree Inorder Traversal (LC 94): root = [1,null,2,3]
Mistake: returns [1, 2, 3]Fix: returns [1, 3, 2]
Gotcha 2: Looping while stack instead of while node or stack
Mistake
```
while stack:
```
Fix
```
while node or stack:
```
What happens: stack is empty at the start, and node holds the root. With while stack, the loop body never runs, and the function returns []. The same mistake also appears in the middle of a walk. After the last node on stack is popped, node can still point at a right subtree that has not been walked, while stack is empty.
Example: root = [1,null,2,3]
Mistake: returns []Fix: returns [1, 3, 2]
Gotcha 3: Popping a node in postorder without checking top.right is not last
Mistake
```
if order == "post" and top.right:
```
Fix
```
if order == "post" and top.right and top.right is not last:
```
What happens: In postorder, the walk comes back to a node twice before it leaves it: once from the left subtree and once from the right subtree. top.right is not last tells the two returns apart. Without it, the second return sees top.right again and walks into the right subtree again. On [1,null,2,3], the loop never ends.
Example: root = [1,null,2,3], order = "post"
Mistake: the loop never endsFix: returns [3, 2, 1]
Gotcha 4: Comparing top.right.val with last.val instead of the nodes
Mistake
```
if order == "post" and top.right and (last is None or top.right.val != last.val):
```
Fix
```
if order == "post" and top.right and top.right is not last:
```
What happens: Different nodes can hold the same value. In [1,1,1], the left child (last) and the right child (top.right) both hold 1, so the test decides that the right subtree is finished. The root is popped, and the right child is never visited. The result is [1, 1] instead of [1, 1, 1]. is not compares the nodes themselves.
Example: root = [1,1,1], order = "post"
Mistake: returns [1, 1]Fix: returns [1, 1, 1]
Gotcha 5: Walking a deep tree with recursion
Mistake
```
def walk(node):
    if node:
        walk(node.left)
        result.append(node.val)
        walk(node.right)
```
Fix
```
while node or stack:
    while node:
        stack.append(node)
        node = node.left
    node = stack.pop()
    result.append(node.val)
    node = node.right
```
What happens: Each recursive call waits for the call below it, so the call stack is as deep as the tree is high. Python stops at about 1000 nested calls and raises RecursionError. A chain of 3000 nodes fails. Binary Tree Inorder Traversal (LC 94) has at most 100 nodes, but Binary Search Tree Iterator (LC 173) allows 10^5 nodes, which can form one chain. A list named stack lives on the heap and has no such limit.
Example: root = a chain of 3000 nodes, each the left child of the one before
Mistake: raises RecursionErrorFix: returns 3000

Canonical LeetCode:Binary Tree Inorder Traversal (LC 94)Binary Tree Preorder Traversal (LC 144)Binary Tree Postorder Traversal (LC 145)Binary Search Tree Iterator (LC 173)

Open the Tree Traversals card

Built on the mental models above

Construct Binary TreeTree Construction (Build from Preorder + Inorder)
The recursion works on index ranges of the two traversals, and the next preorder value is the root of each range.
Tree Diameter DPTree DP (Max Path Sum / Diameter)
The function returns one downward leg, and a separate global_max records the best path that bends at each node.
Two Tree WalkTwo-Tree DFS (Walking a Pair of Nodes Together)
The call takes a pair of nodes, one from each tree, and combines the pair with the answers of its two child pairs.
Tree State DPTree State DP (Return Several States per Node)
Each call returns one best value per state of the node, such as taken and skipped, so the parent never looks at grandchildren.
RerootRerooting a Tree (Answer for Every Root)
A second pass walks down and hands each child the answer for everything outside its subtree, so every node gets the answer as if it were the root.
Tree As StringTree as a String (Serialize and Canonical Key)
Each call returns a string built from its children's strings, so equal subtrees give equal strings that can be counted or compared.
Rewire TreeRewire Tree (Return the Node That Stays)
Each call returns the node that stays in its place, which may be None, and the parent stores that return value as its child.
Greedy Tree DPGreedy Postorder Tree DP (Distribute Coins, Minimum Fuel Cost)
Each subtree returns one signed number, what it holds minus what it needs, and the parent counts that many crossings of the edge above it.
BST BoundsBST Property / Range Validation
The value passed down is a pair (low, high), and the BST rule picks the single branch to follow.
Root-to-Leaf PathsRoot-to-Leaf Path Backtracking
The path above is a shared list: append before the recursive calls, pop after them, and copy it at a leaf.
BST InorderInorder Traversal as a Sorted Stream (Kth Smallest in BST, BST Iterator)
An inorder walk visits a BST in ascending order, so it can stop as soon as it has the value it needs.

The DFS Decision Rule

When facing an unseen binary tree or recursive graph problem, ask these questions in order:

Step 1.Does the problem optimize an arbitrary path that can bend/turn at any node (diameter, maximum path sum)?

➔ Tree Diameter DP

Binary Tree Maximum Path Sum (LC 124)Diameter of Binary Tree (LC 543)

Update global maximum with 2-legged summit (node.val + left + right); return strictly 1-legged branch (node.val + max(left, right)) upward.

Step 2.Is each node a choice (take it or not, covered or not) tied to its children's choices, so one number per subtree can't say which choice its root made?

➔ Tree State DP

House Robber III (LC 337)Binary Tree Cameras (LC 968)

Return one best total per state of the node, e.g. (rob, skip), and combine the children's tuples in the parent.

Step 3.Is the problem a greedy tree-covering decision driven by each child's status (e.g. minimum cameras, moving coin surplus/deficit)?

➔ Greedy Tree DP

Distribute Coins in Binary Tree (LC 979)Minimum Fuel Cost to Report to the Capital (LC 2477)

Bubble each child's status or surplus up from the postorder call; the parent acts only when a child needs it and counts what crosses each edge.

Step 4.Is the input a Binary Search Tree (BST) that you validate, search, insert into, delete from or trim?

➔ BST Bounds

Validate Binary Search Tree (LC 98)Lowest Common Ancestor of a Binary Search Tree (LC 235)

Propagate open intervals (low, high) downward or steer recursion down a single branch based on directional comparison.

Step 5.Does the problem list the nodes of a tree in a named order (preorder, inorder or postorder), or ask for that order without recursion?

➔ Tree Traversals

Binary Tree Inorder Traversal (LC 94)Binary Tree Preorder Traversal (LC 144)

Walk with an explicit stack and change only the line that calls visit: on the way down for preorder, after the left subtree for inorder, after the right subtree for postorder.

Step 6.Is the input a BST and the answer depends on its values in sorted order (k-th smallest, gaps between neighbours, an iterator)?

➔ BST Inorder

Kth Smallest Element in a BST (LC 230)Minimum Absolute Difference in BST (LC 530)

Walk inorder (left, node, right), iteratively with a stack when you must stop early, and count on the pop.

Step 7.Does the problem require reconstructing full root-to-leaf paths?

➔ Root-to-Leaf Paths

Path Sum II (LC 113)Binary Tree Paths (LC 257)

Mutate a single shared buffer on entry (append), snapshot deep copies at true leaves (list(path)), and pop on exit to restore state for sibling branches.

Step 8.Does evaluating the current node require knowing ancestral context (e.g. running maximum, path prefix sum)?

➔ Top-Down DFS

Count Good Nodes in Binary Tree (LC 1448)Path Sum (LC 112)

Pass accumulated constraints downward via arguments: dfs(child, max(ancestor_max, node.val)).

Step 9.Does the problem give you two trees, or one tree compared with itself, and ask whether they match, mirror each other or merge, so each answer pairs a node of one tree with a node of the other?

➔ Two Tree Walk

Same Tree (LC 100)Symmetric Tree (LC 101)

Step 10.Does the problem compare the subtrees of one tree with each other (which shapes repeat, or whether one tree appears inside another), or ask for a text form of a tree?

➔ Tree As String

Find Duplicate Subtrees (LC 652)Serialize and Deserialize Binary Tree (LC 297)

Return a string from every call, built from the node value and the strings of its two children, with a marker for a missing child: equal subtrees give equal strings, so count or compare the strings.

Step 11.Does the problem ask for a deleted, pruned or rewired tree: remove some nodes and return the roots that remain, or cut leaves that match a rule?

➔ Rewire Tree

Delete Nodes And Return Forest (LC 1110)Binary Tree Pruning (LC 814)

Return from every call the node that should stay in its place, or None: set node.left = rewire(node.left) and node.right = rewire(node.right) first, then decide whether this node stays.

Step 12.Does the problem ask for an answer for every node as if that node were the root (the sum of distances from each node, the cost to reach all nodes from each start)?

➔ Reroot

Sum of Distances in Tree (LC 834)Count Number of Possible Root Nodes (LC 2581)

Run one pass up the tree to get each subtree's counts and sums, then one pass down that hands each child the answer for everything outside its subtree.

Step 13.Does the problem ask for an aggregate property or structural transform of the whole tree (depth, height, balance, invert, or LCA)?

➔ Bottom-Up DFS

Maximum Depth of Binary Tree (LC 104)Balanced Binary Tree (LC 110)

Recursively solve left and right subtrees independently; synthesize answers upon return: return combine(node.val, dfs(left), dfs(right)).

Step 14.Do you get two traversal orders of one tree with distinct values and must rebuild it?

➔ Construct Binary Tree

Construct Binary Tree from Preorder and Inorder Traversal (LC 105)Construct Binary Tree from Inorder and Postorder Traversal (LC 106)

The first preorder value is the root; its index in inorder (from a value-to-index map) splits the left and right subtrees; recurse on each.

Step 15.Are there many 'where do I land after k steps up' questions (k-th ancestor, LCA), with k and the query count too large to walk one step at a time?

➔ Binary Lifting

Kth Ancestor of a Tree Node (LC 1483)Minimum Edge Weight Equilibrium Queries in a Tree (LC 2846)

Precompute up[j][v] = up[j-1][up[j-1][v]], then answer a jump of k with the 2^j jumps of k's set bits.

Pattern Architecture & Invariant Design Masterclass

Because trees are connected acyclic graphs with exactly one path between any two nodes, a parent node can solve its own problem simply by synthesizing the already-solved answers of its children.

Code / Blueprint

       [ Parent Node ]
          /        \
   (left_res)    (right_res)
      /              \
[ Left Subtree ]   [ Right Subtree ]
 (Solved fully)     (Solved fully)

The breakthrough mental model for mastering Tree DFS is the Recursive Leap of Faith, and most tree DFS frames follow this 3-step cycle:

🛑 The Floor — Base Case Check (if not node: return base_val): When node is None or a leaf is reached, return the mathematical identity element (e.g. 0 for depth, None for trees, True for validity). This anchors the recursion — without it, the call stack recurses infinitely.
🌿 The Leap of Faith — Divide & Recurse (left = dfs(node.left), right = dfs(node.right)): Trust that dfs(node.left) and dfs(node.right) return 100% correct, complete solutions for their respective subtrees. Do not trace the recursion in your head. Left and right subtrees have zero shared state (Subtree Independence Invariant).
💎 The Synthesis — Combine & Bubble Up (return combine(node.val, left, right)): Write only the combine logic that builds the parent's answer from node.val, left_res, and right_res, then return that value upward. When this frame returns, its subtree is fully resolved and its stack memory is immediately freed.

The 3-Step Recursive Frame Lifecycle

Interactive Architecture Diagram

Synthesizing vector architecture diagram...

Variable Anatomy: The 7 Variables Every Tree DFS Uses

Code / Blueprint

def dfs(node: Optional[TreeNode], min_val: float, max_val: float, path: list[int]) -> int:
    if not node:
        return 0                                    # 1. base_val (Recursion floor)
    
    path.append(node.val)                           # 2. path (Current branch accumulator)
    left_res = dfs(node.left, min_val, node.val, path)   # 3. left_res (Left subtree answer)
    right_res = dfs(node.right, node.val, max_val, path) # 4. right_res (Right subtree answer)
    path.pop()                                      # 5. un-choose (Backtrack step)
    
    return max(left_res, right_res) + 1             # 6. combine (Bubble-up synthesis)

Variable	Type / Role	Purpose in Tree DFS	Failure Mode if Missing / Mismanaged
`node`	`Optional[TreeNode]`	Pointer to current tree node being evaluated in active call frame.	Infinite recursion if `node.left` / `node.right` not advanced.
`base_val`	`int / bool / None`	Neutral mathematical identity returned when hitting empty branch (`None`).	Returning wrong base (e.g. `1` instead of `0`) shifts depth off-by-one.
`left_res`	`Any (int, bool, Node)`	Fully solved result returned by left subtree recursive call.	Tracing recursion manually leads to cognitive overload.
`right_res`	`Any (int, bool, Node)`	Fully solved result returned by right subtree recursive call.	Must be treated symmetrically or pruned in BSTs.
`low` / `high`	`float / int`	Top-down inherited bounds passed downwards to validate search space.	Checking only immediate child `left < node < right` misses deep BST violations.
`path`	`list[int]`	Shared mutable buffer tracking active root-to-leaf path.	Appending `path` directly without `list(path)` copies mutates recorded results.
`global_max`	`list[int]` / `nonlocal`	Global accumulator tracking cross-subtree values (e.g. Tree Diameter, Max Path Sum).	Returning local branch sum while neglecting bending path across root.

The 3 Dimensions of Tree DFS

Every Tree DFS problem can be classified across 3 orthogonal dimensions:

Code / Blueprint

                      DIMENSION 1: INFORMATION FLOW
               ┌───────────────────────┴───────────────────────┐
               ▼                                               ▼
     Bottom-Up Synthesis                              Top-Down Accumulation
   (Post-Order Return Values)                      (Pre-Order Parameter Passing)
   e.g. Max Depth, Balanced Tree                   e.g. Valid BST, Good Nodes
 
                      DIMENSION 2: TRAVERSAL ORDER
       ┌───────────────────────┼───────────────────────┐
       ▼                       ▼                       ▼
   Pre-Order               In-Order                Post-Order
 (Root → L → R)          (L → Root → R)          (L → R → Root)
 Path Accumulation       BST Monotonic Sort      Subtree Synthesis
 
                   DIMENSION 3: CALL-STACK BOUND O(H)
               ┌───────────────────────┴───────────────────────┐
               ▼                                               ▼
         Balanced Tree                                   Skewed Chain
        H = O(log N)                                      H = O(N)

Dimension 1: Information Direction (Bottom-Up vs Top-Down):
- Bottom-Up: Parent answers depend on child answers. Recurse first, combine on return (Post-Order).
- Top-Down: Child validity depends on ancestor constraints. Pass running bounds downward in arguments (Pre-Order).
Dimension 2: Traversal Order (Pre vs In vs Post):
- Pre-Order (Root → Left → Right): Work happens before recursion (path building, serialization).
- In-Order (Left → Root → Right): Work happens between children. On BSTs, yields strictly sorted ascending values.
- Post-Order (Left → Right → Root): Work happens after recursion (height calculations, subtree deletion, inversion).
Dimension 3: Call-Stack Memory Bound ( $O(H)$ ):
- Auxiliary memory is strictly bounded by tree height $H$ .
- Balanced Tree: $H = O(\log N)$ stack frames.
- Degenerate Skewed Chain: $H = O(N)$ stack frames (can cause recursion depth overflow).

The 5 Master Tree DFS Paradigms

Code / Blueprint

┌─────────────────────────────────────────────────────────────────────────────┐
│                       THE 5 MASTER TREE DFS PARADIGMS                       │
├────────────────────────────────┬────────────────────────────────────────────┤
│ 1. Pure Divide & Conquer       │ Bottom-up return bubbling: LC 104, 110, 236│
│ 2. In-Place Tree Mutation      │ Post-order subtree swapping: LC 226, 114   │
│ 3. Top-Down Parameter Passing  │ Ancestor constraint propagation: LC 1448   │
│ 4. BST Monotonic / Split       │ Exploiting sorted order & bounds: LC 98,235│
│ 5. Tree Backtracking (Paths)   │ Mutable buffer choose-explore-unchoose: 113│
└────────────────────────────────┴────────────────────────────────────────────┘

Understanding Invariants: Subtree Independence & Memory Bound

Base Floor Anchor & Out-of-Bounds Pruning

Condition: If node is None

Action: return neutral algebraic base identity (0 for depth/count, None for tree pointers, True for validity) immediately

Terminates recursive descent at leaf boundaries without creating non-existent child frames, maintaining O(N) total calls.

Monotonic Range & Branch Elimination Pruning

Condition: In a BST: target < node.val (pruning right) or target > node.val (pruning left); or ancestor bounds violation: not (low < node.val < high)

Action: Prune the infeasible child branch immediately; do not dispatch recursive call

Spatial monotonicity guarantees target values cannot exist in the pruned branch, reducing time complexity from O(N) full traversal to O(H) single-path search.

Common Questions

"When my code calls dfs(root.left) and then dfs(root.right), how should I picture what's happening — does the current node handle both sides at the same time, or does execution go all the way down the left side first, come back up, and only then start the right side?"

You need both mental models — you just use them at different times.
- While you are designing the algorithm, use the Delegation mindset: at the current node, you explore both left and right.
- While you are tracing or debugging a program, use the Stack mindset: the machine goes all the way down the left branch, pops all the way back up, and only then goes down the right branch.
1. The Design mindset — think locally (Delegation). Writing a recursive function while trying to visualize the entire call stack diving down and popping back up will overwhelm your working memory. Instead, treat dfs as a subcontractor: you are standing at the current node, and you say "I need the answer for my left side — go figure that out and hand it back to me," then "I need the answer for my right side — go get that too." This is exactly the Recursive Leap of Faith from the mental model above: you trust that dfs(node.left) and dfs(node.right) each return a complete, correct answer, and you never trace how they got there. You only care about what comes back to the current frame. This is what makes designing Tree DP tractable — you focus on one question: "What information do I pass down to my children, and what information do I need them to pass back up to me?"

2. The Debug mindset — think procedurally (Stack). When your code is failing, or you're reading someone else's recursive solution (like a Tree DP zigzag-path walk), switch to the computer's actual execution order. The computer cannot do two things at once: when it hits dfs(node.left), it fully suspends the current frame and dives all the way down the left subtree, hitting leaf after leaf until it returns None/base case. Only after the entire left subtree has finished and popped off the call stack does execution return to the current frame and finally start dfs(node.right).

The takeaway: when you're staring at a blank editor trying to solve a tree problem, don't try to picture the execution diving down and popping back up — that mindset is for verifying code, not writing it. Stay in the Delegation mindset: focus on one single node, and ask what it needs from its children and what it owes its parent.
"In problems like Binary Tree Maximum Path Sum, why do we need both a global_max variable AND a return value from dfs — isn't the return value enough?"

Because they answer two different questions, and a parent can only make use of one of them.

The return value answers "what is the best score my parent can extend a path through, using just me and one of my children?" A path can only continue upward through a single leg — a parent can't accept a path that already bent at you and also keep extending it, because a path can't fork twice. That's why the return is node.val + max(left_gain, right_gain): exactly one leg, chosen greedily.

global_max answers a completely different question: "what is the best score of any path that is allowed to bend at this exact node, using both legs at once?" That path can never be extended further — it already used both directions — so it can only ever update a running best-so-far, never be returned upward.

Every node computes both from the same two recursive calls: global_max = max(global_max, node.val + left_gain + right_gain) (the two-legged "summit," compared against the global best) and return node.val + max(left_gain, right_gain) (the single-legged branch, handed to the parent). Conflating the two — returning the two-legged value, or forgetting to update the global with it — is the single most common bug in this archetype. max(..., 0) on each leg is the other half: a path is always allowed to decline a negative subtree rather than drag the total down.

Coach discussion points

1.
"Your recursive function uses no explicit data structures. Why is its space complexity not $O(1)$ ?" $\to$ Call-stack frames consume $O(H)$ auxiliary RAM ( $O(N)$ on skewed trees).
2.
"Why must BST validation pass ranges downward rather than checking left and right children locally?" $\to$ Subtree validity is a global invariant across all ancestors.
3.
"When does a problem require post-order vs pre-order traversal?" $\to$ Post-order when parent needs child results; pre-order when child needs ancestor context.

Complexity analysis

Metric	Balanced Tree	Skewed Chain Tree	Derivation / Mechanism
Time Complexity	$O(N)$	$O(N)$	Every node is entered once and left once; work per frame is $O(1)$ .
Auxiliary Space	$O(\log N)$	$O(N)$	Memory bounded strictly by call stack frame depth (tree height $H$ ).
Path Copying (LC 113)	$O(N \log N)$	$O(N)$	Snapshotting `list(path)` at $K$ matching leaves costs $O(H)$ per match, $O(N \cdot H)$ in all. A chain has one leaf, so one copy. The $O(N^2)$ worst case is a caterpillar: about $N/2$ leaves, up to $N/2$ deep (4000 nodes copy 2,003,000 values).

Production Systems Deployment & Motivation

Mastery Roadmap & Prerequisite Graph

Base case floor error: Returning 1 instead of 0 when node is None. An empty tree has depth 0, while a leaf node has depth 1. Returning 1 shifts every path depth by +1.
Skewed tree call-stack overflow: In degenerate linked-list trees ( $O(N)$ height), deep recursion triggers stack overflow. Production systems require iterative stack traversal (stack = [(root, 1)]).
Node count vs edge count ambiguity: LeetCode defines depth as the number of nodes along the path (root alone = 1). Graph theory often counts edges (root alone = 0). Always clarify unit definitions.

Staff+ Engineering Perspective

Staff+ Systems Architecture & Hardware Considerations

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES