Difficulty: EasyTrees

Diameter of Binary Tree

Problem in Plain English

Given the root of a binary tree, return the number of edges on the longest path between any two nodes. That longest path may or may not pass through the root.

Problem Statement

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter is the longest path between any two nodes, measured in edges rather than nodes, and it may or may not pass through the root.

Constraints

The number of nodes is between 1 and 10000, inclusive.
Each node value is between -100 and 100, inclusive; only the tree shape affects the diameter.

Examples

Example 1

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

The path 4 → 2 → 1 → 3 has 3 edges. Path 5 → 2 → 1 → 3 ties it. The two child heights at root 1 are 2 and 1, while the candidate at node 2 has only 2 edges.

Example 2

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

The only nonempty path joins 1 to 2 with one edge. Root 1 combines child heights 1 and 0; node 2 contributes a candidate of 0.

Example 3

Input: root = [1]
Output: 0

A single node has no edge to traverse. Both child heights are 0, so the diameter is 0 even though the tree height is 1.

Example 4

Input: root = [1,2,null,3,4,5,null,null,6]
Output: 4

The longest path is 5 → 3 → 2 → 4 → 6, entirely below root 1. At node 2 the child heights are 2 and 2, giving 4 edges; root 1 combines heights 3 and 0, giving only 3.

Intuition

A path between two nodes has one highest node, where its two downward arms meet. Height counts nodes below a child, with an empty child having height 0: those child heights also count the edges from their parent to the deepest descendants. In Example 1, root 1 joins left height 2 and right height 1 into 3 edges. The winning highest node can be below the root, so compare this sum at every node; return only a single downward height to its parent.

Approaches

Top Down Recompute

Solution Details

Reveal Top Down Recompute: intuition, complexity, and code

Intuition

Measure both child heights from scratch at every node, then keep the largest sum. This directly enumerates every possible meeting point of a path, but descendants are measured again for each ancestor. An explicit depth-first stack keeps the straightforward recomputation approach runnable even on a 10000-node chain.

Step-by-Step Logic

Use a pending-node stack to visit every candidate meeting point. Start with root 1 in Example 1 and best = 0; measure each child subtree with its own stack of node/depth pairs, starting depth 1.
During the left height walk, node 2 has depth 1 and nodes 4 and 5 have depth 2; its height is 2. The right walk visits only node 3 at depth 1, so its height is 1. Update best with their sum, obtaining 3.
Push the right child before the left so the next meeting point is node 2. Remeasure leaves 4 and 5 as height 1 each; its candidate 2 cannot beat best = 3.
Continue visiting nodes 4, 5 and 3 in stack order. Each has two empty children with height 0, so every candidate is 0 and best stays 3. Return best after the pending stack is empty.

Why It Works

The height walk carries a depth for each pending node and records the maximum depth reached, so it returns the exact node-height of its subtree. Every simple path in a tree has a unique highest node; its endpoints descend into different child subtrees, or one endpoint is that highest node. At a fixed meeting node, joining the two deepest child descents gives the longest possible path through it, with exactly leftHeight + rightHeight edges. Visiting every node includes the meeting point of the global longest path. Taking the maximum therefore finds the diameter, and no child reference or value is modified.

Dry Run

Top Down Recompute: variable states at each step
Event in execution order	Pending stack (bottom → top)	Height depth transitions	left, right; candidate	best
Start	[1]	not yet measured	pending	0
Pop 1; measure left 2	[]	(2,1): maximum 0 → 1; push (5,2),(4,2); (4,2): 1 → 2; (5,2): stays 2	left = 2	0
Measure right 3 and finish 1	[3,2] after pushing children	(3,1): maximum 0 → 1	2,1; 3	0 → 3
Pop 2; remeasure both leaves	[3,5,4] after pushing children	(4,1): 0 → 1; separate walk (5,1): 0 → 1	1,1; 2	3 → 3
Pop 4	[3,5]	both empty: height 0	0,0; 0	3 → 3
Pop 5	[3]	both empty: height 0	0,0; 0	3 → 3
Pop 3; return	[]	both empty: height 0	0,0; 0	answer 3

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(h)

Here n is the node count and h is the tree height. Every candidate node rewalks its descendants: on a chain the walks total (n-1) + (n-2) + … + 1, giving quadratic worst-case time; a balanced tree takes O(n log n). The pending-node stack and one active height stack each hold O(h) entries. Repeatedly allocated depth entries do not accumulate across height calls, so peak auxiliary space is O(h), worst-case O(n). The result is one integer, no tree nodes are copied, and explicit stacks avoid recursion-depth settings.

Code

Solution.java

1import java.util.ArrayDeque;2import java.util.Deque;3
4class TreeNode {5    int val;6    TreeNode left, right;7    TreeNode(int val) { this.val = val; }8}9
10class Solution {11    private static class Entry {12        TreeNode node;13        int depth;14        Entry(TreeNode node, int depth) { this.node = node; this.depth = depth; }15    }16
17    private int height(TreeNode root) {18        if (root == null) return 0;19        Deque<Entry> stack = new ArrayDeque<>();20        stack.push(new Entry(root, 1));21        int maximum = 0;22        while (!stack.isEmpty()) {23            Entry entry = stack.pop();24            maximum = Math.max(maximum, entry.depth);25            // Depth counts nodes here; from the candidate parent it counts edges.26            if (entry.node.right != null) stack.push(new Entry(entry.node.right, entry.depth + 1));27            if (entry.node.left != null) stack.push(new Entry(entry.node.left, entry.depth + 1));28        }29        return maximum;30    }31
32    public int diameterOfBinaryTree(TreeNode root) {33        if (root == null) return 0;34        Deque<TreeNode> pending = new ArrayDeque<>();35        pending.push(root);36        int best = 0;37        while (!pending.isEmpty()) {38            TreeNode node = pending.pop();39            // Check every meeting point, including those below the root.40            best = Math.max(best, height(node.left) + height(node.right));41            if (node.right != null) pending.push(node.right);42            if (node.left != null) pending.push(node.left);43        }44        return best;45    }46}

Hints

Hint 1

The longest path through one node joins its deepest left descent with its deepest right descent.

Hint 2

Check that candidate at every node, because the winning path can hide entirely inside one subtree.

Hint 3

Compute heights bottom-up so each subtree height is measured once and reused by its parent.

Edge Cases

A single node has height 1 but diameter 0, because the answer counts edges.
A 10000-node left, right or alternating chain has diameter 9999; explicit stacks avoid deep recursive calls.
The longest path can be wholly inside one subtree, as in Example 4; checking only the root misses it.
Duplicate, negative and zero values change neither heights nor diameter; node identity, not value, defines the structure.
Although the stated input is nonempty, these snippets also return 0 for null. Every input node and child reference stays unchanged across repeated calls.

Common Mistakes and Interview Tips

Adding an extra 1 to the child-height sum: with empty height 0, leftHeight + rightHeight already counts edges.
Returning the diameter candidate as the height sent upward; a parent can extend only one child arm, so return 1 + max(leftHeight, rightHeight).
Resetting best at each frame, or retaining it as an uncleared object field between calls; keep it local to the current invocation.
Combining a frame before both child heights are available, or failing to set last to 0 for an absent child, reuses an unrelated previous height.
Claiming the recomputation approach is linear or that explicit stacks use constant space: repeated descents cost quadratic time on a chain, and a deep post-order walk stores O(h) frames.
Assuming recursive snippets fit the valid 10000-node depth. Explain post-order first, then use explicit frames when runtime call-stack limits are tighter than the input bound.

Key Takeaway

Return child summaries upward while updating a shared best, which turns repeated top-down measuring into one bottom-up pass.