Pattern #39

Tree Depth First Search (DFS)

Important interview questions, thinking patterns, call stack movement, state flow directions (Downward vs Upward), Preorder vs Postorder, and Go code templates.

Must Solve

18 core questions — solve these first.

1.Maximum Depth of Binary Tree
1 + max(dfs(left), dfs(right)) - Return height upwardeasy
2.Same Tree
Preorder check: root values match + sameTree(left) && sameTree(right)easy
3.Invert Binary Tree
Preorder swap: swap node.Left & node.Right then DFS subtreeseasy
4.Symmetric Tree
Mirror check: isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)easy
5.Balanced Binary Tree
Postorder height check: return -1 if unbalanced in single DFSeasy
6.Diameter of Binary Tree
Postorder: update global max(leftHeight + rightHeight), return 1 + max(left, right)easy
7.Path Sum
Pass remaining sum downward to leaves: targetSum - node.Val == 0 at leafeasy
8.Path Sum II
DFS + Backtracking: append node -> recurse -> remove nodemedium
9.Binary Tree Paths
DFS carrying current string path downward to leaf nodeseasy
10.Lowest Common Ancestor of a Binary Tree
Postorder: return node if root == p or q; check if left != nil && right != nilmedium
11.Binary Tree Maximum Path Sum
Postorder: global max(node.Val + max(0,left) + max(0,right)), return node.Val + max(0, max(left, right))hard
12.Subtree of Another Tree
Preorder traverse main tree, calling isSameTree(node, subRoot) at each nodeeasy
13.Count Good Nodes in Binary Tree
Pass maxValSeen downward: count if node.Val >= maxValSeenmedium
14.Sum Root to Leaf Numbers
Pass current accumulator downward: currSum = currSum * 10 + node.Valmedium
15.House Robber III
Postorder Tree DP returning [robCurrent, skipCurrent] tuplemedium
16.Flatten Binary Tree to Linked List
Reverse Postorder (Right -> Left -> Root) maintaining prev pointermedium
17.Construct Binary Tree from Preorder and Inorder Traversal
Preorder first = root. Inorder index splits left & right subtrees (use HashMap)medium
18.Serialize and Deserialize Binary Tree
Preorder string with null markers "#" (e.g. 1,2,#,#,3,#,#)hard

Also Important

10 more questions worth practicing.

19.Minimum Depth of Binary Tree
Postorder DFS return min(left, right) handling single child non-null caseseasy
20.Sum of Left Leaves
Preorder DFS tracking isLeft boolean flag for leaf nodeseasy
21.Maximum Difference Between Node and Ancestor
Pass minVal & maxVal downward from root to leafmedium
22.Longest Univalue Path
Postorder DFS matching child values to current node valuemedium
23.Path Sum III
Preorder DFS + Prefix Sum Map tracking running sum countsmedium
24.Delete Leaves With a Given Value
Postorder leaf deletion: node.Left = remove(node.Left), check if now leafmedium
25.Find Leaves of Binary Tree
Postorder height grouping: leaves at height 0, parent at height 1medium
26.Binary Tree Cameras
Postorder state DP: 0 (uncovered), 1 (has camera), 2 (covered)hard
27.Smallest Subtree with all Deepest Nodes
Postorder DFS returning (depth, lcaNode) tuplemedium
28.All Nodes Distance K in Binary Tree
DFS annotate parent pointers, then BFS/DFS distance K from target nodemedium

How to Think

Need explore every subtree?Tree DFS (Recursion / Call Stack)
Need height / depth / diameter?DFS + return result UPWARD
Need root-to-leaf path?DFS + carry state DOWNWARD
Need children solved before parent?Postorder DFS (Left-Right-Root)
Need root before children?Preorder DFS (Root-Left-Right)

Go Tree DFS Code Templates

Preorder & Postorder DFS Templates in Go

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// 1. Preorder DFS: Root -> Left -> Right (Processing Root First)
func preorderDFS(root *TreeNode) {
    if root == nil {
        return
    }

    // Process current node first (e.g. serialize, copy, path build)
    fmt.Println(root.Val)

    preorderDFS(root.Left)
    preorderDFS(root.Right)
}

// 2. Postorder DFS: Left -> Right -> Root (Processing Children First)
func postorderDFS(root *TreeNode) int {
    if root == nil {
        return 0
    }

    leftHeight := postorderDFS(root.Left)
    rightHeight := postorderDFS(root.Right)

    // Process current node using children answers!
    return 1 + max(leftHeight, rightHeight)
}

👉 Total Time: O(N) | Space: O(H) recursion stack

State Flow Directions: Downward vs Upward

1. Downward State (Parameters)

Parent passes parameters down to children. Used in Path Sum II, Good Nodes, Max/Min Ancestor Diff.

2. Upward Result (Return Values)

Children calculate results and return them back up to parent. Used in Max Depth, Diameter, Max Path Sum, Balanced Tree.

Preorder vs Postorder Traversal Use Cases

Preorder (Root -> Left -> Right): Process current node before children. Best for Serialization, Tree Copying, Path Building, Flattening.

Postorder (Left -> Right -> Root): Process children before current node. Best for Height, Diameter, Balanced Tree, Subtree DP (House Robber III), Delete Leaves.

// Path Sum II (DFS + Backtracking Template)
func pathSum(root *TreeNode, targetSum int) [][]int {
    result := [][]int{}
    currentPath := []int{}

    var dfs func(node *TreeNode, remaining int)
    dfs = func(node *TreeNode, remaining int) {
        if node == nil {
            return
        }

        // 1. Append to current path
        currentPath = append(currentPath, node.Val)
        remaining -= node.Val

        // 2. Check if leaf node matching target
        if node.Left == nil && node.Right == nil && remaining == 0 {
            pathCopy := make([]int, len(currentPath))
            copy(pathCopy, currentPath)
            result = append(result, pathCopy)
        }

        // 3. Recurse subtrees
        dfs(node.Left, remaining)
        dfs(node.Right, remaining)

        // 4. Backtrack cleanup!
        currentPath = currentPath[:len(currentPath)-1]
    }

    dfs(root, targetSum)
    return result
}

Visual Memory Rule

DOWNWARD  → Carry state in function parameters (current path / remaining sum)
UPWARD    → Return result from recursion (height / max single branch gain)
Postorder → Children answer first (Height / Subtree DP)
Preorder  → Process root first (Path building / Serialization)

💡 Golden Rule: "Decide what information goes down to the children and what answer comes back up to the parent."

Common Interview Mistakes

1. Forgetting Nil Base Case

Always write if node == nil { return ... } at the start of your DFS function!

2. Not Defining DFS Meaning

Before writing code, explicitly state what dfs(node) returns (e.g. subtree height, max single branch path sum).

3. Recomputing Subtrees Repeatedly

Calling a separate DFS helper inside another DFS loop results in O(N²)! Return all required info in one single DFS traversal.

4. Forgetting Backtracking Cleanup

When carrying a shared mutable slice (path), remember to slice back path = path[:len(path)-1] after exploring subtrees!

Interview Rules

1. Subtree traversal / path problem? → Tree DFS
2. Children answers needed first?→ Postorder DFS (Left -> Right -> Root)
3. Root processed before children?→ Preorder DFS (Root -> Left -> Right)
4. State from parent to child? → Pass parameters DOWNWARD
5. Result from children to parent? → Send return values UPWARD
6. Root-to-leaf paths? → DFS + Backtracking (append -> recurse -> remove)
7. Negative child branch gain? → Ignore it using max(0, childGain)
8. Overall Complexity → Time: O(N) | Recursive Stack Space: O(H) (O(log N) balanced, O(N) skewed)

Small Rules

Rule 1: Always handle nil base case first (if node == nil { return ... }).
Rule 2: Clearly define what dfs(node) returns before writing code.
Rule 3: Parameters carry state DOWNWARD; return values send results UPWARD.
Rule 4: Postorder evaluates children first; Preorder evaluates root first.
Rule 5: Backtracking on shared path slices requires popping the last element after subtrees return.

Production Thinking

Directory File System Search → Recursively traversing folder trees deep down one path first

DOM / UI Component Trees → Collecting nested component elements & applying style transformations

Software Dependency Trees → Walking package dependency subtrees (requires cycle check for graphs)

Organization Hierarchy Search → Finding all subordinates under a manager via subtree DFS

Remember This

Tree DFS        → Go deep
Base case       → nil
Preorder        → Root Left Right
Inorder         → Left Root Right
Postorder       → Left Right Root
Path info       → Pass DOWNWARD
Subtree info    → Return UPWARD
Height          → Postorder
Diameter        → Heights + Global
LCA             → Results come upward
Time            → O(N)
Space           → O(Height)

💡 Golden Rule: "Decide what information goes down to the children and what answer comes back up to the parent."