LeetCode 543 · Easy · Trees

Diameter of Binary Tree

Find the length of the longest path between any two nodes of a binary tree, counted in edges. The path may or may not pass through the root.

O(n)time
O(h)space · call stack
DFSheight up · left + right at each node

level order as on LeetCode, null = no child · 1 to 15 nodes, 4 levels · values −99 to 99

Call stack one frame per dfs call · newest on the right · badges = returned height

private int res;public int diameterOfBinaryTree(TreeNode root) { res = 0; dfs(root); return res;}private int dfs(TreeNode root) { if (root == null) { return 0; } int left = dfs(root.left); int right = dfs(root.right); res = Math.max(res, left + right); return 1 + Math.max(left, right);}
root
—
left
—
right
—
res
0
return
—

Why it works

  1. Brute force measures every pair of nodes (or, per node, recomputes both subtree heights from scratch): O(n²) on a long chain.
  2. Every path has one highest node. There it bends: it goes down the left side and down the right side. So the longest path through a node is height(left) + height(right) edges, and the answer is the best such sum over all nodes.
  3. One post-order pass gives both. Each call returns its height to the parent and, on the way, offers left + right to the global res. Every node is visited once: O(n) time, O(h) stack.
  4. Pitfall: returning the diameter instead of the height. The parent needs the height to extend a path; a bent path cannot be extended upward, so it only updates res.
  5. Same shape: Binary Tree Maximum Path Sum (124) uses this exact pattern with sums instead of edge counts, and Balanced Binary Tree (110) with a height difference.