Diameter of Binary Tree
Problem
root of a binary tree, return the length of its
longest path between any two nodes, measured in edges. The path does not
have to go through the root.[1,2,3,4,5]Output3 (4→2→1→3)[1,2]Output11 ≤ n ≤ 104 · -100 ≤ Node.val ≤ 100
Try it yourself
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
}
}
height(left) + height(right). A post-order pass that returns heights
can update the best answer at every node for free.Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.
Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.
Open the Tree DFS guide →Approaches
Brute ForceHeight Recomputed at Every Node
O(n²)Space O(h)For each node, compute both subtree heights from scratch and treat it as the path's top; recurse into both children and keep the max. Heights of deep nodes are recomputed by every ancestor (O(n log n) if balanced, O(n²) if skewed).
public int diameterOfBinaryTree(TreeNode root) { if (root == null) return 0; int through = height(root.left) + height(root.right); int best = Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)); return Math.max(through, best); } private int height(TreeNode node) { // number of nodes on the longest downward path if (node == null) return 0; return 1 + Math.max(height(node.left), height(node.right)); }
Direct translation of the definition, but repeats the same height work.
BetterMemoized Heights (HashMap)
O(n)Space O(n)The waste is recomputing height. Cache it per node in a
HashMap, so each node's height is computed once and every later lookup
is O(1).
private final Map<TreeNode, Integer> memo = new HashMap<>(); public int diameterOfBinaryTree(TreeNode root) { if (root == null) return 0; int through = height(root.left) + height(root.right); int best = Math.max(diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right)); return Math.max(through, best); } private int height(TreeNode node) { if (node == null) return 0; Integer cached = memo.get(node); if (cached != null) return cached; int h = 1 + Math.max(height(node.left), height(node.right)); memo.put(node, h); return h; }
Linear time, but an extra map of n entries plus hashing overhead.
OptimalSingle Post-Order Pass
O(n)Space O(h)Let the recursion return the height to the parent, while on the side it
updates maxDiameter with leftH + rightH — the best
path whose top is this node. One visit per node, no map.
private int maxDiameter = 0; public int diameterOfBinaryTree(TreeNode root) { height(root); return maxDiameter; } private int height(TreeNode node) { if (node == null) return 0; int leftH = height(node.left); int rightH = height(node.right); maxDiameter = Math.max(maxDiameter, leftH + rightH); // path topped at node return 1 + Math.max(leftH, rightH); }
One pass, only the recursion stack — the standard answer.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Height Recomputed at Every Node | O(n²) | O(h) |
| Better | Memoized Heights (HashMap) | O(n) | O(n) |
| Optimal | Single Post-Order Pass | O(n) | O(h) |
- Returning
height(left) + height(right)of the root only — the longest path may skip the root. - Counting nodes instead of edges (off by one).
- Returning the diameter instead of the height to the parent — the two must stay separate.
- Draw a tree whose longest path lives entirely in the left subtree.
- Clarify the unit: edges, not nodes.
- Explain the O(n²) → O(n) jump: compute height once and reuse it.