LeetCode: Finding the Diameter of a Binary Tree

The 'Diameter of a Binary Tree' (LeetCode #543) might sound tricky, but it's actually quite straightforward once we understand what it means. Put simply, the diameter is the longest path between two nodes in a binary tree. Knowing how to solve this problem helps us get comfortable with recursion and tree traversal and makes other tree‑based problems easier to tackle.
In this article, I'll do my best to clearly break down exactly what the diameter means, show you how to solve it step‑by‑step, and share a practical solution in JavaScript/TypeScript.
Understanding What 'Diameter' Means
Before diving into solving this problem, let's quickly clarify what the diameter of a binary tree actually is. It's the longest route between any two nodes in the tree, measured by counting the number of edges (connections between nodes). It's important to remember this route doesn't always pass through the root.
Here's a quick visual example:
1
/ \
2 3
/ \
4 5The longest path here is either 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3. Both of these paths have three edges, so the diameter is 3.
Breaking the Problem down Clearly
Treat each node as a possible highest point of a path. The longest downward branch on its left and the longest downward branch on its right give us the longest path through that node. We compare that candidate with the best one found elsewhere in the tree; the highest point need not be the root or the middle of the path.
The neat thing is that we can find this with just one traversal of the tree if we approach it correctly.
A Practical Recursive Solution
Since trees naturally lend themselves to recursion, that's exactly what we'll use here. Let's look at a practical example in TypeScript...
TypeScript Example for the Diameter
type TreeNode = {
val: number;
left: TreeNode | null;
right: TreeNode | null;
};
const diameterOfBinaryTree = (root: TreeNode | null): number => {
let diameter = 0;
const findDepth = (node: TreeNode | null): number => {
if (!node) return 0;
const left = findDepth(node.left);
const right = findDepth(node.right);
diameter = Math.max(diameter, left + right);
return Math.max(left, right) + 1;
};
findDepth(root);
return diameter;
};What's Actually Happening Here?
The helper returns a downward height; the outer function remembers the largest diameter found anywhere. That distinction explains the steps below:
- The depth‑first traversal computes each node's result after computing the results for its children.
- At each node, we calculate how far down we can go on the left side and on the right side.
- We add these two lengths together to see if we've found a longer path than before.
- Finally, we return the longest path discovered anywhere in the tree.
We calculate one candidate diameter per node, using the two child heights already returned by the recursion. We do not enumerate every possible pair of endpoints, which is why a single traversal is enough.
How Efficient is This Solution?
One reason this solution works well is that we only visit each node once:
Time Complexity:
O(n), each node gets visited exactly one time.Space Complexity:
O(h), withhbeing the tree's height, because of recursion.
The running time is linear, but the recursive call stack still depends on the tree's height. A very deep, unbalanced tree can exceed JavaScript's stack limit. The iterative version below keeps the same height calculation without relying on nested function calls.
Computing the Same Heights Without Recursion
The challenge permits up to 10,000 nodes. If those nodes form a single chain, the recursive version has to keep 10,000 calls waiting for their child to return. I'd use an explicit stack for that case. The part worth preserving is the order of work: a parent needs both child heights before it can calculate its own.
This is a postorder traversal. The first time a node comes off the stack, we schedule it to come back after its children. The second time, their heights are ready. childrenVisited records which of those two jobs we're doing; it doesn't mean we've finished the parent.
type TreeNode = {
val: number;
left: TreeNode | null;
right: TreeNode | null;
};
export const diameterOfBinaryTreeIterative = (
root: TreeNode | null
): number => {
if (!root) return 0;
const heights = new Map<TreeNode, number>();
const stack: { node: TreeNode; childrenVisited: boolean }[] = [
{ node: root, childrenVisited: false },
];
let diameter = 0;
while (stack.length > 0) {
const { node, childrenVisited } = stack.pop()!;
if (!childrenVisited) {
stack.push({ node, childrenVisited: true });
if (node.right) {
stack.push({ node: node.right, childrenVisited: false });
}
if (node.left) {
stack.push({ node: node.left, childrenVisited: false });
}
continue;
}
const leftHeight = node.left ? heights.get(node.left)! : 0;
const rightHeight = node.right ? heights.get(node.right)! : 0;
diameter = Math.max(diameter, leftHeight + rightHeight);
heights.set(node, Math.max(leftHeight, rightHeight) + 1);
}
return diameter;
};The parent goes back on the stack first, followed by its right child and then its left child. Because the stack removes the last entry first, the left subtree finishes, then the right subtree finishes, and only then do we return to the parent. Either child order would work; keeping the parent underneath both is the essential part.
The height map uses the node object as its key. Two different nodes can have the same val, so their values wouldn't be safe keys. No pointers or values in the supplied tree are changed; the stack and map hold the traversal state separately.
The non‑null assertions have specific reasons. The loop only pops a nonempty stack, and a present child has already had its height stored before its parent is processed. A missing child contributes 0. As with the recursive example, the input must be an actual tree, not a structure containing cycles or shared child nodes.
Following the Return Journey
Take a chain of three nodes, each the left child of the one above it. We first schedule all three. The leaf then stores height 1 and contributes a diameter of 0. Its parent reads that height, stores height 2, and contributes a diameter of 1. Finally, the root reads height 2 and contributes a diameter of 2. Those are the two edges connecting the three nodes.
A branching tree uses exactly the same calculation. Once both child heights are available, their sum counts the edges in the longest path through that parent. The running maximum also remembers candidates from lower down. That's why the final answer still works when the longest path never reaches the root.
I check that distinction with a tree whose root has only one child, but whose lower subtree has two long branches. The path between those branches can beat every path through the root. A single chain wouldn't catch an implementation that only calculated the root's candidate.
This version takes O(n) time under the usual hash‑map cost model: every node is scheduled twice, and its height is calculated once. The explicit stack uses O(h) space, but the map retains one height per node, so the total auxiliary space is O(n). The recursive version uses O(h) call‑stack space instead. That's the trade‑off here: more stored results, with no dependence on how many recursive calls the runtime will allow.
I checked the new function against a separate all‑pairs distance calculation on small trees, including every binary‑tree shape through eight nodes and generated trees. I also checked left, right, and alternating chains of 10,000 nodes: each returns 9,999. Node identities, links, and values stay unchanged. These checks support the implementation; the child‑before‑parent ordering is the reason it works.
Easy Mistakes and How to Avoid Them
Here are a couple of common mistakes to keep in mind when solving this kind of problem:
Thinking Diameter Always Goes through the Root
Remember, the diameter doesn't always include the root node. Always look for paths anywhere in the tree, not just through the root.
Confusing Diameter and Height
The diameter here counts edges between two endpoints. In this implementation, findDepth() counts nodes on the longest downward path: an empty subtree has height 0, and a leaf has height 1. Other definitions count height in edges, so make the chosen convention explicit before combining the values.
Wrapping Up
Key Takeaways
- The diameter is simply the longest path between any two nodes in a tree.
- A postorder traversal computes child heights before the parent, using either recursion or an explicit stack.
- Clearly tracking both left and right depths at each node simplifies the solution.
- Understanding common pitfalls helps avoid easy mistakes.
At each node, left + right counts the edges in the longest path through that node. Each child's node height equals the number of edges from the current node down that branch. The function then returns Math.max(left, right) + 1: the longer child path's node count, plus the current node itself. For a leaf, that means a returned height of 1 and a candidate diameter of 0.
Postscript
November 2026: I've added a postorder version that doesn't use recursion, so you can work through a tree with 10,000 nodes in a chain without relying on the runtime's call‑stack depth. I've also made the extra height‑map storage explicit, so the comparison with my recursive example includes the memory trade‑off.