Given the root of a binary tree, return the length of the diameter of the tree. The diameter is the length of the longest path between any two nodes (measured in number of edges). This path may or may not pass through the root.

Examples

Example 1:

Input: root = [1,2,3,4,5]
      1
     / \
    2   3
   / \
  4   5
Output: 3
Explanation: The longest path is [4,2,1,3] or [5,2,1,3], both length 3.

Example 2:

Input: root = [1,2]
Output: 1

Constraints

  • The number of nodes is in [1, 10^4]
  • -100 <= Node.val <= 100

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Thinking Process

Key Observation

The diameter passing through a node = left depth + right depth + 2 (counting edges). The overall diameter is the maximum of this across all nodes.

Why Bottom-Up?

We need the depth of every subtree. Computing depth top-down would recompute subtrees repeatedly (O(n^2)). Instead, compute depth bottom-up and update a global maximum at each node – same pattern as LC 110 Balanced Binary Tree.

Edge Count vs Node Count

Returning -1 for a null node means a leaf has depth 0, and the path through a node with left depth L and right depth R has L + R + 2 edges. This correctly counts edges rather than nodes.

Walk-Through

      1
     / \
    2   3
   / \
  4   5

Node 4: left=-1, right=-1 → diameter candidate = -1+-1+2 = 0, return 0
Node 5: left=-1, right=-1 → diameter candidate = 0, return 0
Node 2: left=0,  right=0  → diameter candidate = 0+0+2 = 2, return 1
Node 3: left=-1, right=-1 → diameter candidate = 0, return 0
Node 1: left=1,  right=0  → diameter candidate = 1+0+2 = 3, return 2

Max diameter = 3 ✓
Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Approach: Bottom-Up DFS – O(n)

Input: root = [1,2,3,4,5]
Output: 3
# Tree:    1
#         / \
#        2   3
#       / \
#      4   5
# Longest path: 4 → 2 → 1 → 3 (or 5 → 2 → 1 → 3), 3 edges.

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: ### Key Observation

Walkthrough — input root = [1,2,3,4,5], expected output 3:

The longest path is [4,2,1,3] or [5,2,1,3], both length 3.

Common Mistakes

  • Returning 0 for null instead of -1 (off-by-one: counts nodes instead of edges)
  • Forgetting the diameter may not pass through the root – must track the global max across all nodes
  • Returning the diameter from the recursive function instead of the single-side depth (the function returns depth, but updates diameter as a side effect)

Key Takeaways

  • Bottom-up DFS with global max is a recurring tree pattern: compute a per-node value bottom-up, update a global answer at each node
  • Same structure as LC 110 (sentinel) and LC 124 (max path sum) – learn one, get all three
  • The return -1 for null trick cleanly handles edge counting

References

Template Reference