Tree Diameter

1. 1.Diameter of Binary Tree
   Postorder DFS: candidate = leftHeight + rightHeight, return 1 + max(leftHeight, rightHeight)easy
2. 2.Diameter of N-ary Tree
   Collect height of all children, sum top 2 largest child heights for candidatemedium
3. 3.Diameter of an Undirected Tree
   Two BFS/DFS passes: BFS from arbitrary node to farthest A, then BFS from A to farthest Bmedium
4. 4.Longest Path Between Any Two Tree Nodes
   Same as Tree Diameter: track max path across all subtreesmedium
5. 5.Binary Tree Maximum Path Sum
   Candidate = node.Val + max(0, left) + max(0, right), return node.Val + max(0, max(left, right))hard
6. 6.Longest Univalue Path
   Postorder DFS: extend path only if child.Val == node.Valmedium
7. 7.Tree Diameter Using Two BFS / DFS
   Two-pass algorithm: 1st search finds endpoint A, 2nd search finds endpoint B & distancemedium
8. 8.Minimum Height Trees
   Trim leaf nodes layer-by-layer (Kahn algorithm / topological sort) until 1 or 2 centers remainmedium
9. 9.Tree Distances
   Rerooting Tree DP: 1st DFS computes distances from root, 2nd DFS shifts root to children in O(1)hard
10. 10.Farthest Node in a Tree
    Run BFS/DFS from target node to find node at max distancemedium

1. 11.Longest Path With Different Adjacent Characters
   Postorder DFS: combine top 2 child branches where child.Char != node.Charhard
2. 12.Longest ZigZag Path in a Binary Tree
   DFS tracking direction (0 for left, 1 for right) & current path lengthmedium
3. 13.Maximum Path Between Two Leaves
   Postorder DFS: candidate updated ONLY at nodes with BOTH left and right children non-nilhard
4. 14.Weighted Tree Diameter
   Accumulate edge weights instead of +1 per edge in two BFS/DFS passesmedium
5. 15.Tree DP Longest Path Variants
   Postorder state returns tracking longest and 2nd longest downward pathsmedium

How to Think

1. Need longest path between any two nodes?Tree Diameter
2. Binary Tree?Postorder DFS + Height
3. At each node?leftHeight + rightHeight
4. General undirected tree?Two BFS / DFS passes

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

// 1. Binary Tree Diameter (Single-Pass Postorder DFS)
func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter := 0

    var height func(node *TreeNode) int
    height = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftH := height(node.Left)
        rightH := height(node.Right)

        // Update global diameter (uses BOTH branches!)
        if leftH+rightH > maxDiameter {
            maxDiameter = leftH + rightH
        }

        // Return height upward (returns ONE branch!)
        return 1 + max(leftH, rightH)
    }

    height(root)
    return maxDiameter
}

// 2. General Undirected Tree Diameter (Two BFS Passes)
func treeDiameterUndirected(n int, edges [][]int) int {
    adj := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u)
    }

    bfs := func(start int) (int, int) {
        dist := make([]int, n)
        for i := range dist { dist[i] = -1 }
        queue := []int{start}
        dist[start] = 0
        farthestNode, maxD := start, 0

        for len(queue) > 0 {
            curr := queue[0]
            queue = queue[1:]
            for _, neighbor := range adj[curr] {
                if dist[neighbor] == -1 {
                    dist[neighbor] = dist[curr] + 1
                    if dist[neighbor] > maxD {
                        maxD = dist[neighbor]
                        farthestNode = neighbor
                    }
                    queue = append(queue, neighbor)
                }
            }
        }
        return farthestNode, maxD
    }

    farthestA, _ := bfs(0)
    _, diameter := bfs(farthestA)
    return diameter
}

Height vs Diameter & Single-Pass DFS

Two-Pass BFS Trick for Undirected Trees

Tree Diameter   → Longest path between ANY two nodes (May NOT pass through Root!)
Binary Tree     → Candidate = leftHeight + rightHeight | Return = 1 + max(left, right)
Edges vs Nodes  → N nodes path = N-1 edges (Check problem definition!)
Undirected Tree → Two BFS passes (Arbitrary -> Farthest A -> Farthest B)

Common Interview Mistakes

Interview Rules

1. 1. Longest path between any two nodes? → Tree Diameter
2. 2. Binary Tree strategy? → Postorder DFS returning height
3. 3. Candidate diameter at node? → leftHeight + rightHeight
4. 4. Return value upward to parent? → 1 + max(leftHeight, rightHeight)
5. 5. Passes through root? → Not necessarily! Update global max at every node
6. 6. General undirected tree strategy?→ Two BFS/DFS passes (Arbitrary -> Farthest A -> Farthest B)
7. 7. Max Path Sum comparison? → Max Path Sum sums node values; Diameter sums edge counts
8. 8. Overall Complexity → Time: O(N) | Stack Space: O(H) (O(log N) balanced, O(N) skewed)

Tree Diameter   → Longest path
Binary Tree     → Postorder DFS
Left + Right    → Candidate diameter
Return          → 1 + max(left, right)
Global answer   → Update everywhere
Root            → Not necessarily on path
General Tree    → BFS/DFS twice
Time            → O(N)

💡 Golden Rule: "Each node asks: ‘What is the deepest path from my left, and what is the deepest path from my right?’ Their sum may be the diameter."