Pattern #37

Binary Trees

Important interview questions, thinking patterns, main recursive pattern (Left + Right combine), Mirror symmetry, Diameter vs Max Path Sum, and Go templates.

Must Solve

20 core questions — solve these first.

1.Maximum Depth of Binary Tree
1 + max(maxDepth(left), maxDepth(right))easy
2.Same Tree
Check root values + sameTree(p.Left, q.Left) && sameTree(p.Right, q.Right)easy
3.Invert Binary Tree
Swap node.Left and node.Right recursively at every nodeeasy
4.Symmetric Tree
Mirror check helper: left.Left == right.Right && left.Right == right.Lefteasy
5.Balanced Binary Tree
Return height or -1 if |leftHeight - rightHeight| > 1 in single DFSeasy
6.Diameter of Binary Tree
Global max(leftHeight + rightHeight), return 1 + max(leftHeight, rightHeight)easy
7.Binary Tree Level Order Traversal
BFS Queue: process levelSize elements per loop iterationmedium
8.Binary Tree Right Side View
BFS level order taking last element, or DFS right child firstmedium
9.Path Sum
Pass remaining sum downward to leaves: targetSum - node.Val == 0 at leafeasy
10.Path Sum II
Backtracking path sum passing current slice downward to leavesmedium
11.Lowest Common Ancestor of a Binary Tree
If root == p or q return root. If left != nil && right != nil return rootmedium
12.Binary Tree Maximum Path Sum
Global max(node.Val + max(0,left) + max(0,right)), return node.Val + max(0, max(left, right))hard
13.Subtree of Another Tree
Check isSameTree(root, subRoot) || isSubtree(root.Left) || isSubtree(root.Right)easy
14.Count Good Nodes in Binary Tree
Pass maxValSeen downward: count if node.Val >= maxValSeenmedium
15.Construct Binary Tree from Preorder and Inorder Traversal
Preorder first = root. Inorder index splits left & right subtrees (use HashMap)medium
16.Serialize and Deserialize Binary Tree
Preorder string with null markers "#" (e.g. 1,2,#,#,3,#,#)hard
17.Flatten Binary Tree to Linked List
Reverse Postorder (Right -> Left -> Root) maintaining prev pointermedium
18.Binary Tree Zigzag Level Order Traversal
BFS level order reversing alternate level slicesmedium
19.All Nodes Distance K in Binary Tree
Annotate parent pointers via DFS, then BFS distance K from target nodemedium
20.Maximum Width of Binary Tree
BFS level order with positional 1-based indexing (2*i, 2*i+1) taking rightIdx - leftIdx + 1medium

Also Important

10 more questions worth practicing.

21.Minimum Depth of Binary Tree
DFS return min(left, right) handling single child non-null caseseasy
22.Sum of Left Leaves
DFS tracking isLeft boolean flag for leaf nodeseasy
23.Binary Tree Paths
Backtracking strings stringifying paths to leaveseasy
24.Cousins in Binary Tree
BFS level order tracking node parent & deptheasy
25.Vertical Order Traversal
DFS/BFS tracking (col, row, val) + Map[col] sortmedium
26.Boundary Traversal
Left boundary + Leaves + Right boundary (bottom-up)medium
27.House Robber III
Tree DP returning [robNode, skipNode] tuple for each nodemedium
28.Binary Tree Cameras
Postorder state DP: 0 (uncovered), 1 (has camera), 2 (covered)hard
29.Find Leaves of Binary Tree
Postorder height grouping: leaves at height 0, parent at height 1medium
30.Delete Leaves With a Given Value
Postorder leaf deletion: node.Left = remove(node.Left), check if now leafmedium

How to Think

Need visit every node?DFS / BFS
Need information from left and right children?Postorder DFS
Need level by level traversal?BFS + Queue
Need root-to-leaf path?DFS + carry state downward
Need longest path / diameter / max path?Get child answers + update global answer

Go Binary Tree Main Recursive Template

Standard 4-Step Recursive Pattern in Go

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

// Main Pattern: 1. Nil Base Case -> 2. Solve Left -> 3. Solve Right -> 4. Combine
func solveTree(node *TreeNode) int {
    // 1. Handle nil base case
    if node == nil {
        return 0
    }

    // 2. Solve left child
    leftResult := solveTree(node.Left)

    // 3. Solve right child
    rightResult := solveTree(node.Right)

    // 4. Combine answers for current node
    return 1 + max(leftResult, rightResult)
}

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

Main Recursive Pattern & Symmetry

Every binary tree node has at most 2 children (Left & Right). The core recursive strategy boils down to:

// Symmetric Tree Mirror Check
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    var isMirror func(left, right *TreeNode) bool
    isMirror = func(left, right *TreeNode) bool {
        if left == nil && right == nil {
            return true
        }
        if left == nil || right == nil || left.Val != right.Val {
            return false
        }
        return isMirror(left.Left, right.Right) && isMirror(left.Right, right.Left)
    }
    return isMirror(root.Left, root.Right)
}

👉 Symmetric trees compare mirror opposite branches across the center vertical line!

Diameter & Maximum Path Sum (Global vs Return Value)

In problems like Diameter or Max Path Sum, there is a fundamental distinction between the global candidate answer and the value returned upward:

// Binary Tree Maximum Path Sum
func maxPathSum(root *TreeNode) int {
    maxSum := -1 << 31 // Global answer accumulator

    var getGain func(node *TreeNode) int
    getGain = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        // Drop negative child contributions (Kadane rule!)
        leftGain := max(0, getGain(node.Left))
        rightGain := max(0, getGain(node.Right))

        // 1. Candidate Global Answer (Uses BOTH branches!)
        currentPathSum := node.Val + leftGain + rightGain
        if currentPathSum > maxSum {
            maxSum = currentPathSum
        }

        // 2. Value Returned Upward (MUST choose ONE branch!)
        return node.Val + max(leftGain, rightGain)
    }

    getGain(root)
    return maxSum
}

Visual Memory Rule

Solve Left  -> Solve Right -> Combine at Node
Global Candidate  → node.Val + left + right (Uses BOTH sides)
Return Upward     → node.Val + max(left, right) (Uses ONE side)
Negative Gain     → max(0, childGain) (Ignore harmful paths!)
Symmetry Mirror   → left.Left <-> right.Right & left.Right <-> right.Left

💡 Golden Rule: "Solve the left subtree, solve the right subtree, then decide what the current node should do with those two answers."

Common Interview Mistakes

1. Forgetting Nil Base Case

Always handle if node == nil { return ... } to prevent dereferencing nil pointers!

2. Returning Both Branches Upward

A path traveling up to a parent CANNOT split into both children! Return node.Val + max(left, right) upward.

3. Assuming Longest Path Passes Root

The tree diameter or maximum path sum may reside entirely within a deep left or right subtree.

4. Confusing Binary Tree With BST

Standard binary trees have NO order guarantee (left < node < right only holds for BSTs).

Interview Rules

1. Max 2 children per node? → Binary Tree
2. Level order traversal? → BFS + Queue FIFO
3. Height / depth / path sum? → DFS + Recursion
4. Diameter of tree? → Global max(leftHeight + rightHeight) updated at every node
5. Symmetry check? → Compare mirror opposite sides (left.Left ↔ right.Right)
6. Negative child path gain? → Ignore it using max(0, childGain)
7. LCA of 2 nodes?→ Return node if root == p or q; check if left != nil && right != nil
8. Overall Complexity → Time: O(N) | DFS Space: O(Height) | BFS Space: O(Width)

Small Rules

Rule 1:Each binary tree node has at most 2 children (Left & Right).
Rule 2: Always handle nil base case first (if node == nil { return ... }).
Rule 3: Global candidate answer uses BOTH children; return value upward uses ONLY ONE branch.
Rule 4: Drop negative child gains with max(0, gain).
Rule 5: Carry path state DOWN, return subtree height/gain UP.

Production Thinking

Expression Trees in Compilers → Syntax trees representing arithmetic (2 + 3) * 4 parsed recursively

Decision Trees in Rules / ML → Yes/No binary decision logic branches evaluated per node

Huffman Coding Compression → Binary compression trees encoding symbols as left (0) / right (1) paths

Hierarchical Condition Evaluation → Evaluating boolean rule trees in production engines

Remember This

Binary Tree     → Left + Right
DFS             → Subtrees / paths
BFS             → Levels
Preorder        → Root first
Inorder         → Root middle
Postorder       → Root last
Height          → child answers upward
Path Sum        → state downward
Diameter        → left height + right height
LCA             → both sides find target
Normal          → Time O(N), Space O(Height)

💡 Golden Rule: "Solve the left subtree, solve the right subtree, then decide what the current node should do with those two answers."