Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter — the longest path between any two nodes. The path does not need to pass through the root. Length is the number of edges on the path.

Examples

Input:  root = [1, null, 2, 3, 4, 5]
Output: 3   (path: 1→2→3→5  or  5→3→2→4, both 3 edges)

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

Constraints

• 1 ≤ number of nodes ≤ 100
• -100 ≤ Node.val ≤ 100

1. Brute Force O(n²)

Intuition

For any node the longest path through it equals height(left) + height(right). Check every node, compare with the best diameter found recursively in each subtree, and take the max.

• Helper maxHeight(node) computes the height of a subtree in O(n).
• diameterOfBinaryTree(node) calls maxHeight for both children and recurses into both subtrees. This re-computes heights for every ancestor — giving O(n²) overall.

Time: O(n²)  |  Space: O(h) recursion stack

2. DFS — Recursive O(n) ★

Intuition

Combine height computation and diameter tracking in a single DFS. The inner function returns the height of the subtree so parents can use it, and as a side effect updates a closure variable res with leftHeight + rightHeight at the current node.

• At each node: left = dfs(root.left), right = dfs(root.right).
• Update res = max(res, left + right) — diameter candidate through this node.
• Return 1 + max(left, right) — the height, used by the caller.
• The visualization shows the DIAMETER counter (amber) update live and green h=N bubbles appear as the recursion returns bottom-up.

Time: O(n) — each node visited once  |  Space: O(h) — O(log n) balanced, O(n) skewed

3. DFS — Iterative (Stack + Map) O(n)

Intuition

Simulate post-order DFS with an explicit stack. A map stores (height, diameter) for each processed node. Before popping a node, ensure both its children are already in the map — if not, push the missing child first. Once both children are ready, pop and compute.

• Stack initialized with root. Map pre-seeded: None → (0, 0) (null node base case).
• Peek the top: if left child missing from map → push left. Else if right child missing → push right. Else pop and compute.
• height = 1 + max(leftH, rightH). diameter = max(leftH + rightH, leftD, rightD).
• Visualization: amber boxes = pending in stack. Green node badge (h=N d=M) = computed and in map. DIAMETER counter tracks the global best.

Time: O(n) — each node processed once  |  Space: O(n) — stack + map

Common Pitfalls

• Returning diameter instead of height from DFS: the DFS helper must returnheight (for the parent to compute its own diameter), not the diameter itself. return left + rightis wrong — it returns a diameter, breaking every ancestor's calculation.
• Assuming the longest path passes through root: it may be entirely inside a subtree. Always track a global res updated at every node.
• Off-by-one — edges vs nodes: the problem counts edges. A single node has diameter 0. Two nodes: 1 edge. Height of a leaf = 1, so leftH + rightH at a node with two leaf children = 1+1 = 2 edges — correct.
• Iterative: not pre-seeding null → (0, 0) in the map: when both children are null the lookup mp[node.left] must succeed. Without the sentinel you get a KeyError / NullPointerException.