Pattern #36

Trees & Binary Trees

Important interview questions, thinking patterns, DFS traversals (Preorder/Inorder/Postorder), BFS level order, LCA, BST validation, and Go tree 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
Helper isMirror(left, right): left.Val == right.Val && left.Left == right.Righteasy
5.Diameter of Binary Tree
Global max(leftHeight + rightHeight), return 1 + max(leftHeight, rightHeight)easy
6.Balanced Binary Tree
Return height or -1 if |leftHeight - rightHeight| > 1 in single DFSeasy
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.Lowest Common Ancestor
If root == p or root == q return root. If left != nil && right != nil return rootmedium
11.Binary Tree Maximum Path Sum
Global max(node.Val + leftGain + rightGain), return node.Val + max(leftGain, rightGain)hard
12.Construct Binary Tree from Preorder and Inorder Traversal
Preorder first = root. Inorder index splits left & right subtrees (use HashMap)medium
13.Validate Binary Search Tree
Carry range bounds: minVal < node.Val < maxVal down recursionmedium
14.Kth Smallest Element in a BST
Inorder traversal yields sorted values: return Kth visited nodemedium
15.Serialize and Deserialize Binary Tree
Preorder string with null markers "#" (e.g. 1,2,#,#,3,#,#)hard
16.Subtree of Another Tree
Check isSameTree(root, subRoot) || isSubtree(root.Left) || isSubtree(root.Right)easy
17.Count Good Nodes in Binary Tree
Pass maxValSeen downward: count if node.Val >= maxValSeenmedium
18.Binary Tree Zigzag Level Order Traversal
BFS level order reversing alternate level slicesmedium
19.Flatten Binary Tree to Linked List
Reverse Postorder (Right -> Left -> Root) maintaining prev pointermedium
20.All Nodes Distance K in Binary Tree
Annotate parent pointers via DFS, then BFS distance K from target nodemedium

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.Path Sum II
Backtracking path sum passing current slice downwardmedium
24.Root to Leaf Paths
Backtracking strings stringifying paths to leaveseasy
25.Cousins in Binary Tree
BFS level order tracking node parent & deptheasy
26.Vertical Order Traversal
DFS/BFS tracking (col, row, val) + Map[col] sortmedium
27.Boundary Traversal
Left boundary + Leaves + Right boundary (bottom-up)medium
28.Binary Tree Cameras
Postorder state DP: 0 (uncovered), 1 (has camera), 2 (covered)hard
29.House Robber III
Tree DP returning [robNode, skipNode] tuple for each nodemedium
30.Recover Binary Search Tree
Inorder DFS detecting swapped adjacent / non-adjacent nodesmedium

How to Think

Need process every node?DFS or BFS
Need depth / height / path information?DFS + Recursion
Need level by level traversal?BFS + Queue
Need information from children first?Postorder DFS
Need root before children?Preorder DFS
Need sorted values from BST?Inorder DFS

Go Binary Tree Code Templates

DFS & BFS Level Order Traversal in Go

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

// DFS Height Pattern: 1 + max(left, right)
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    left := maxDepth(root.Left)
    right := maxDepth(root.Right)
    if left > right {
        return 1 + left
    }
    return 1 + right
}

// BFS Level Order Traversal Pattern using FIFO Queue
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    res := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        level := make([]int, 0, levelSize)

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        res = append(res, level)
    }
    return res
}

👉 Total Time: O(N) | Space: O(H) for DFS, O(W) for BFS

Downward vs Upward Information Travel

Downward State Passing

Parent passes parameters down to children (e.g. remainingSum in Path Sum, maxValSeen in Good Nodes, [minVal, maxVal] bounds in Validate BST).

Upward Result Return

Children calculate results and return them back up to parent (e.g. height in Max Depth, maxSingleBranchGain in Max Path Sum, isBalanced height in Balanced Tree).

Binary Search Tree (BST) & Tree Reconstruction

BST Property: Left subtree values < Node value < Right subtree values. Inorder traversal of a valid BST always yields strictly sorted values!

// Validate BST by carrying range bounds downward: minVal < node.Val < maxVal
func isValidBST(root *TreeNode) bool {
    var validate func(node *TreeNode, minVal, maxVal *int) bool
    validate = func(node *TreeNode, minVal, maxVal *int) bool {
        if node == nil {
            return true
        }
        if (minVal != nil && node.Val <= *minVal) || (maxVal != nil && node.Val >= *maxVal) {
            return false
        }
        return validate(node.Left, minVal, &node.Val) && validate(node.Right, &node.Val, maxVal)
    }
    return validate(root, nil, nil)
}

Visual Memory Rule

Preorder (Root-L-R)   → Root comes first
Inorder (L-Root-R)    → Sorted order for BST
Postorder (L-R-Root)   → Process children before parent
DFS                   → Depth, Path Sum, Height (Recursion / Stack)
BFS                   → Level Order, Shortest Distance (Queue FIFO)

💡 Golden Rule: "For every tree problem, ask: 'What should one node receive from its parent, and what should it return from its children?'"

Common Interview Mistakes

1. Forgetting Nil Base Case

Always check if node == nil { return ... } at the top of your recursive DFS function!

2. Wrong BST Validation

Only checking direct children (left < node && right > node) fails! Must carry global [minVal, maxVal] bounds down the subtree.

3. Recalculating Height Repeatedly

Calling height() recursively at every node turns Balanced Tree check into O(N²)! Return -1 on failure in one single DFS.

4. Confusing Return vs Global Update

In Diameter & Max Path Sum, return ONLY ONE single branch gain upward to parent, but update global answer using BOTH branches!

Interview Rules

1. Process every node? → DFS or BFS
2. Level order traversal? → BFS + Queue FIFO
3. Height / depth / path sum? → DFS + Recursion
4. BST sorted traversal? → Inorder DFS
5. Children results needed first? → Postorder DFS
6. Diameter of tree? → Global max(leftHeight + rightHeight) updated at every node
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: Always handle nil base case first (if node == nil { return ... }).
Rule 2: Preorder visits root first, Inorder visits left then root then right, Postorder visits children first.
Rule 3: BST Inorder traversal produces strictly sorted elements.
Rule 4: Validate BST requires passing minVal and maxVal bounds downward.
Rule 5: Path sum / depth state travels DOWN; height / subtree size / balance returns UP.

Production Thinking

Directory File System Hierarchy → File/folder trees traversed recursively via DFS / BFS

UI DOM Component Layout → HTML DOM tree rendering and event bubbling via postorder/preorder DFS

Corporate Organization Hierarchy → Reporting manager employee hierarchy traversed via subtree DFS

Database Indexing (B-Tree / B+Tree) → Database index page nodes reducing search space from O(N) to O(log N)

Remember This

Tree            → Node + Children
DFS             → Go deep (Recursion / Stack)
BFS             → Level by level (Queue FIFO)
Preorder        → Root Left Right
Inorder         → Left Root Right (Sorted BST)
Postorder       → Left Right Root
BST + sorted    → Inorder
Height / Path   → DFS
Level Order     → Queue
Complexity      → Time: O(N), Space: O(Height) DFS / O(Width) BFS

💡 Golden Rule: "For every tree problem, ask: 'What should one node receive from its parent, and what should it return from its children?'"