Trees: BFS / DFS

One-liner: a tree is a node plus two smaller trees — solve the node by trusting the answers for its subtrees (DFS), or sweep it level by level with a queue (BFS).

The analogy

A company org chart. To count everyone under a manager you do not walk the whole company yourself: you ask each direct report "how many people are under you?", add their answers, and add one for yourself. Every report does the same with their own team. That is DFS recursion. Asking "who is at distance 1 from the CEO, then distance 2, then 3?" is BFS: you process one whole row, then the next.

Recognition signals

1. The input is a binary tree (a *TreeNode) or any hierarchy of parent and children.
2. The question about a node depends on a question about its subtrees: depth, size, balanced, mirror, sum, path.
3. "Level by level", "right side view", "minimum depth" or anything about distance from the root points to BFS.
4. "Is this valid / find the ancestor / any root-to-leaf path" points to DFS.

Step-by-step walkthrough

Max depth of 3,9,20,null,null,15,7:

1. nil has depth 0 (base case).
2. Node 9 and node 15 and node 7 are leaves: each is 1 + max(0, 0) = 1.
3. Node 20 trusts its children: 1 + max(1, 1) = 2.
4. Root 3 trusts both sides: 1 + max(1, 2) = 3.

Nobody needed to know how the others computed their answer — only what they returned.

Code template

// Template (return-value style): solve the node from its children's answers.
// "Trust the subtree": assume solve(child) already returns the right answer for the
// whole child subtree, and only decide how to combine the two answers at this node.
func solve(root *TreeNode) int {
	if root == nil { // base case: the answer for an empty tree
		return 0
	}
	left := solve(root.Left) // trust: correct for the entire left subtree
	right := solve(root.Right)
	return 1 + max(left, right) // combine (this combine step is the only thing that changes)
}

Two styles: return value vs global variable

Return-value style — the function returns exactly what the parent needs, like MaxDepth above. Prefer it when the question's answer is what the parent needs.

Global-variable style — when the answer is not what the parent needs, return one thing and record another. Diameter: the parent needs the height, but the answer is the best bend through any node, stored in an outer best:

// DiameterOfBinaryTree: global-variable style.
// The function RETURNS the height (what the parent needs) but RECORDS the best
// bend through this node in an outer variable (what the question asks).
func DiameterOfBinaryTree(root *TreeNode) int {
	best := 0
	var height func(n *TreeNode) int
	height = func(n *TreeNode) int {
		if n == nil {
			return 0
		}
		l, r := height(n.Left), height(n.Right)
		best = max(best, l+r) // path bending at n uses both sides
		return 1 + max(l, r)
	}
	height(root)
	return best
}

Rule of thumb: if you find yourself wanting to return two different things, return one and keep the other in a captured variable.

DFS recipes

// MaxDepth: number of nodes on the longest root-to-leaf path.
func MaxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + max(MaxDepth(root.Left), MaxDepth(root.Right))
}

// InvertTree: mirror the tree.
func InvertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left, root.Right = InvertTree(root.Right), InvertTree(root.Left)
	return root
}

Validate BST — a node must respect a range inherited from all ancestors, not just its parent. Pass the bounds down:

// IsValidBST: pass the allowed (lo, hi) range down, not just the parent.
// nil bounds mean "unbounded", which also handles Val == MinInt/MaxInt safely.
func IsValidBST(root *TreeNode) bool {
	var check func(n *TreeNode, lo, hi *int) bool
	check = func(n *TreeNode, lo, hi *int) bool {
		if n == nil {
			return true
		}
		if (lo != nil && n.Val <= *lo) || (hi != nil && n.Val >= *hi) {
			return false
		}
		return check(n.Left, lo, &n.Val) && check(n.Right, &n.Val, hi)
	}
	return check(root, nil, nil)
}

Lowest common ancestor — each subtree reports what it found; the node where both sides report is the answer:

// LowestCommonAncestor: trust each subtree to report what it found.
func LowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root // found one target (or fell off the tree)
	}
	left := LowestCommonAncestor(root.Left, p, q)
	right := LowestCommonAncestor(root.Right, p, q)
	if left != nil && right != nil {
		return root // p and q live on different sides: this is the split point
	}
	if left != nil {
		return left
	}
	return right
}

Path sum — information flows down here (the remaining target), and only a leaf may say yes:

// HasPathSum: is there a root-to-leaf path adding up to target?
// Carry the remaining target down; only a LEAF may answer yes.
func HasPathSum(root *TreeNode, target int) bool {
	if root == nil {
		return false
	}
	target -= root.Val
	if root.Left == nil && root.Right == nil {
		return target == 0
	}
	return HasPathSum(root.Left, target) || HasPathSum(root.Right, target)
}

BFS: level order with a queue

DFS goes deep first. BFS visits by distance from the root, using a FIFO queue. Watch it work, with the queue and the result in the variables panel. Input uses the level-order array form; null marks a missing child.

// LevelOrder: BFS with a queue, one level per outer iteration.
func LevelOrder(root *TreeNode) [][]int {
	res := [][]int{}
	if root == nil {
		return res
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue) // freeze: exactly these nodes belong to this level
		level := make([]int, 0, size)
		for i := 0; i < size; i++ {
			n := queue[0]
			queue = queue[1:]
			level = append(level, n.Val)
			if n.Left != nil {
				queue = append(queue, n.Left)
			}
			if n.Right != nil {
				queue = append(queue, n.Right)
			}
		}
		res = append(res, level)
	}
	return res
}

// LevelOrder: BFS with a queue, one level per outer iteration.
func LevelOrder(root *TreeNode) [][]int {
	res := [][]int{}
	if root == nil {
		return res
	}
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue) // freeze: exactly these nodes belong to this level
		level := make([]int, 0, size)
		for i := 0; i < size; i++ {
			n := queue[0]
			queue = queue[1:]
			level = append(level, n.Val)
			if n.Left != nil {
				queue = append(queue, n.Left)
			}
			if n.Right != nil {
				queue = append(queue, n.Right)
			}
		}
		res = append(res, level)
	}
	return res
}

Complexity

Each node is visited once. The difference is the memory: DFS stores one root-to-node path, BFS stores a whole level.

Common mistakes

Practice ladder

Ordered Easy → Hard. For each, decide: what does the recursive call return, and what is the base case?

1. 1.
   Maximum Depth of Binary Tree

   Trust both children; only write the combine step.
   Easy
2. 2.
   Invert Binary Tree
   Easy
3. 3.
   Path Sum

   Carry the remaining target downward.
   Easy
4. 4.
   Diameter of Binary Tree

   What the parent needs and what the question asks differ.
   Easy
5. 5.
   Binary Tree Level Order Traversal

   Process a row at a time.
   Medium
6. 6.
   Validate Binary Search Tree

   A node must respect more than its parent.
   Medium
7. 7.
   Lowest Common Ancestor of a Binary Tree
   Medium
8. 8.
   Construct Binary Tree from Preorder and Inorder Traversal

   The first preorder value splits the inorder array.
   Medium
9. 9.
   Binary Tree Maximum Path Sum

   Return one thing upward, record another globally; negatives can be dropped.
   Hard
10. 10.
    Serialize and Deserialize Binary Tree
    Hard

Which pattern? Drills

Unlabeled problems — pick the pattern, then read why.