Diameter of Binary Tree: One DFS, Height and Diameter Together
Solve Diameter of Binary Tree in O(n) with a single DFS that returns height while tracking the longest through-node path — code, walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
The diameter of a binary tree is the longest path between any two nodes, counted in edges. That path does not have to touch the root — it can live entirely inside a subtree, off to one side.
That single fact is what trips people up. If you assume the answer always runs through the root, you get a fast solution that's wrong on lopsided trees. If you fix that by measuring every path from every node, you get a correct solution that's painfully slow.
The clean answer is one depth-first pass that computes each node's height and, while it's there, checks whether the path bending through that node is the new longest. Height and diameter, measured in the same recursion.
The problem
Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes in the tree. The path may or may not pass through the root.
Input: root = [1, 2, 3, 4, 5]
1
/ \
2 3
/ \
4 5
Output: 3 // longest path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3), 3 edgesTwo things to pin down before writing code:
- The answer is measured in edges, not nodes. A path visiting 4 nodes has 3 edges. A single-node tree has diameter 0.
- The longest path always bends at some node — it goes down into that node's left subtree, up through the node, and down into its right subtree. The length of that bend is
leftHeight + rightHeight.
The brute force baseline
The naive approach follows the definition literally. For every node, compute the height of its left and right subtrees, add them, and keep the largest sum.
function height(node) {
if (node === null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
function diameterOfBinaryTree(root) {
if (root === null) return 0;
const throughRoot = height(root.left) + height(root.right);
const leftBest = diameterOfBinaryTree(root.left);
const rightBest = diameterOfBinaryTree(root.right);
return Math.max(throughRoot, leftBest, rightBest);
}This is correct, but it re-walks the tree constantly. diameterOfBinaryTree visits every node, and at each node it calls height, which itself descends the whole subtree. Height gets recomputed for the same nodes over and over — the root's subtree heights, then its children's, then their children's. On a skewed tree that's O(n²). The wasted work is entirely redundant: height never changes, so computing it more than once per node is pure overhead.
The key insight
The fix is a classic recursion trick: make one function do two jobs at once. A single DFS can return a node's height to its parent while, as a side effect, updating a running maximum diameter.
Why does this work? Every path in the tree bends at exactly one highest node. At that node, the path's length is leftHeight + rightHeight. So if you're already computing height at every node — and height DFS naturally visits every node exactly once — you can compute that bend for free during the same visit and keep the best one in an outer variable.
The height you return upward is 1 + max(leftHeight, rightHeight): the longest single branch down to a leaf. The diameter you record is leftHeight + rightHeight: both branches joined through the current node. Same two subtree heights, used two different ways.
The optimal solution
This is exactly the algorithm the visualizer steps through. An outer maxDiameter accumulates the best bend; the inner height function returns a height and updates that accumulator on every node.
function diameterOfBinaryTree(root) {
let maxDiameter = 0;
function height(node) {
if (node === null) return 0;
const left = height(node.left);
const right = height(node.right);
maxDiameter = Math.max(maxDiameter, left + right);
return 1 + Math.max(left, right);
}
height(root);
return maxDiameter;
}The order inside height is what makes it work. Both recursive calls finish before the diameter update, so left and right are the true subtree heights when you sum them. This is post-order traversal: children first, then the node. The return line hands the height up to the parent; the maxDiameter line is a quiet side effect that outlives the recursion.
Because a null child returns height 0, leaves compute left + right = 0 — a leaf is a path of zero edges, which is correct.
Walkthrough
Trace root = [1, 2, 3, 4, 5]. DFS finishes children before parents, so nodes resolve in post-order: 4, 5, 2, 3, 1. Each row shows the two subtree heights available at that node, the bend left + right, the running max, and the height returned upward.
| Node | leftH | rightH | left + right | maxDiameter after | height returned |
|---|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 |
| 2 | 1 | 1 | 2 | 2 | 2 |
| 3 | 0 | 0 | 0 | 2 | 1 |
| 1 | 2 | 1 | 3 | 3 | 3 |
Node 4 and 5 are leaves: both children are null, so their heights are 0, their bend is 0, and each returns height 1. Node 2 then sees leftH = 1 (from 4) and rightH = 1 (from 5), a bend of 2 — the new record. Node 3 is a leaf, bend 0, no change. Node 1 finally sees leftH = 2 (the taller side, from subtree 2) and rightH = 1 (from node 3), a bend of 3, which wins. Final answer: 3 edges, the path 4 → 2 → 1 → 3.
Notice node 1's bend of 3 beats node 2's bend of 2 here — but on a differently shaped tree, the winning bend could easily sit at node 2 and never involve the root at all. That's the case the brute-force root-only assumption gets wrong.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (recompute height) | O(n²) | O(h) | height re-walks each subtree at every node |
| Single DFS | O(n) | O(h) | one visit per node; recursion stack depth = tree height h |
The optimal version touches each node exactly once and does constant work per node, so it's linear in the number of nodes. The space is the recursion stack, which grows to the tree's height h — O(log n) for a balanced tree, O(n) for a fully skewed one.
Common mistakes
- Assuming the path goes through the root. The longest path can live entirely in one subtree. Track a global maximum across all nodes, not just
height(root.left) + height(root.right). - Counting nodes instead of edges. A path through 4 nodes has 3 edges. Because a
nullreturns height 0 and a leaf's bend is0 + 0 = 0, this code counts edges automatically — don't add 1 to "fix" it. - Updating the max after returning. The
maxDiameterline must run before thereturn, usingleftandrightwhile you still have them. Once you return, those subtree heights are gone. - Recomputing height inside the diameter recursion. That's the O(n²) trap. Let one post-order pass return height and update the diameter together — never call a separate
heighthelper per node.
Where this pattern shows up next
The "return one value up while updating a global on the side" DFS is a whole family of tree problems:
- Maximum Depth of Binary Tree — the pure height recursion this solution is built on top of.
- Maximum Depth of Binary Tree - Top Down — the same height, computed by passing depth downward instead of returning it up.
- Balanced Binary Tree — return height, and on the side flag any node where the two subtree heights differ by more than one.
- Path Sum — a root-to-leaf DFS that carries a running total down the tree.
You can also step through Diameter of Binary Tree interactively to watch heights bubble up and the max diameter update node by node.
FAQ
Why is the diameter of a binary tree measured in edges instead of nodes?
The diameter is defined as the length of the longest path, and a path's length is its edge count. A path visiting 4 nodes crosses 3 edges. This code counts edges naturally because a null child contributes height 0 and a leaf's bend is 0 + 0 = 0. If you wanted the node count instead, you would add 1 to the final answer, but the standard problem asks for edges.
Does the longest path always pass through the root?
No, and this is the single most common bug. The longest path can sit entirely inside a subtree, never touching the root. That's why the solution keeps a global maxDiameter and checks the bend leftHeight + rightHeight at every node, then returns the overall maximum — rather than only measuring the path through the root.
What is the time and space complexity of the optimal solution?
Time is O(n): the DFS visits each of the n nodes exactly once and does constant work per node. Space is O(h), where h is the height of the tree — the depth of the recursion call stack. That's O(log n) for a balanced tree and O(n) in the worst case of a completely skewed tree. The brute-force version that recomputes height at every node is O(n²).
Why does the code update maxDiameter before returning the height?
Because both values come from the same two subtree heights, left and right. The diameter through the current node is left + right, while the height returned to the parent is 1 + max(left, right). The update has to happen while left and right are still in scope — after the return, the function has exited and those values are gone. Post-order (children first, then the node) guarantees both are the true, finished subtree heights when you use them.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.