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   5

The 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?

This code might look complicated at first glance, but it's really straightforward:

• 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), with h being 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 the JavaScript runtime's stack limit; an iterative traversal is worth considering when that depth is possible.

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 single depth‑first traversal with recursion efficiently solves the problem.
• 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.