Solving Diameter of Binary Tree in JavaScript: Step-by-Step Guide

Introduction to the Diameter of a Binary Tree

The diameter of a binary tree is a classic problem that frequently appears in coding interviews and algorithm challenges. It refers to the length of the longest path between any two nodes in the tree. This path may or may not pass through the root, which is a common misconception that trips up many developers. Understanding how to compute this efficiently is essential for anyone working with tree-based data structures in JavaScript.

What Is the Diameter?

Formally, the diameter is defined as the number of edges on the longest path between two nodes. Consider a tree where the left subtree is very deep and the right subtree is shallow. The longest path might travel from the deepest leaf of the left subtree up to the root and down to another leaf. However, it could also be entirely contained within one subtree, never touching the root at all.

Because of this, a naive approach that only checks paths passing through the root will produce incorrect results. We need a strategy that examines every node as a potential "turning point" of the longest path.

Why This Problem Matters

The diameter problem is more than an academic exercise. It teaches several fundamental concepts that apply broadly in software engineering:

• Tree traversal techniques: You must understand depth-first search (DFS) to solve it efficiently.
• Recursive thinking: The optimal solution relies on breaking the problem into smaller subproblems.
• Global state management: You learn how to track a maximum value across recursive calls without recomputing it.
• Time complexity awareness: Comparing brute-force and optimized approaches highlights the value of algorithmic thinking.

In real-world applications, similar traversal patterns appear in network routing, organizational hierarchy analysis, file system exploration, and dependency graph evaluation. Mastering this problem builds a foundation for tackling those scenarios.

Defining the Tree Structure

Before solving the problem, we need a binary tree node representation. In JavaScript, we typically define a node using a class with a value and pointers to left and right children.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Example tree:
//       1
//      / \
//     2   3
//    / \
//   4   5
const root = new TreeNode(
  1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);

This structure allows us to build any binary tree and traverse it recursively. The example tree above has a diameter of 3, which corresponds to the path 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3.

The Brute-Force Approach

A straightforward but inefficient approach is to compute the height of the left and right subtrees for every node, sum them to get the path length through that node, and keep track of the maximum. The problem is that computing the height repeatedly leads to redundant work.

function height(node) {
  if (node === null) return 0;
  return 1 + Math.max(height(node.left), height(node.right));
}

function diameterBruteForce(root) {
  if (root === null) return 0;

  // Longest path that passes through the current node
  const pathThroughRoot = height(root.left) + height(root.right);

  // Longest path entirely within the left or right subtree
  const leftDiameter = diameterBruteForce(root.left);
  const rightDiameter = diameterBruteForce(root.right);

  return Math.max(pathThroughRoot, leftDiameter, rightDiameter);
}

This solution works correctly, but its time complexity is O(n²) in the worst case (a skewed tree), because the height function is called for every node, and each call itself traverses the subtree. For large trees, this becomes prohibitively slow.

The Optimized DFS Solution

The key insight is that we can compute the height of each subtree once while simultaneously updating the diameter. By performing a single post-order traversal, we calculate the height of each node's left and right subtrees, use those values to compute the candidate diameter at that node, and update a global maximum.

This reduces the time complexity to O(n), where n is the number of nodes, since each node is visited exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

function diameterOfBinaryTree(root) {
  let maxDiameter = 0;

  function dfs(node) {
    if (node === null) return 0;

    const leftHeight = dfs(node.left);
    const rightHeight = dfs(node.right);

    // The longest path through this node uses both subtree heights
    maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);

    // Return the height of this node to its parent
    return 1 + Math.max(leftHeight, rightHeight);
  }

  dfs(root);
  return maxDiameter;
}

Let's break down how this works step by step:

• We declare maxDiameter outside the helper function so it persists across all recursive calls.
• The dfs function returns the height of the subtree rooted at the given node.
• At each node, the longest path that "turns" at this node is the sum of the left and right subtree heights.
• We update maxDiameter if this candidate path is longer than any previously found.
• We return the height (not the diameter) so the parent node can perform its own calculation.

Tracing Through an Example

Using the example tree from earlier, let's trace the execution:

//       1
//      / \
//     2   3
//    / \
//   4   5

console.log(diameterOfBinaryTree(root)); // Output: 3

The traversal proceeds as follows:

• Visit node 4: leftHeight = 0, rightHeight = 0, candidate = 0, returns height 1.
• Visit node 5: leftHeight = 0, rightHeight = 0, candidate = 0, returns height 1.
• Visit node 2: leftHeight = 1, rightHeight = 1, candidate = 2, maxDiameter = 2, returns height 2.
• Visit node 3: leftHeight = 0, rightHeight = 0, candidate = 0, returns height 1.
• Visit node 1: leftHeight = 2, rightHeight = 1, candidate = 3, maxDiameter = 3, returns height 3.

The final answer is 3, which matches the expected result.

Handling Edge Cases

A robust solution must account for edge cases that often appear in tests and interviews:

// Empty tree
console.log(diameterOfBinaryTree(null)); // 0

// Single node
const single = new TreeNode(42);
console.log(diameterOfBinaryTree(single)); // 0

// Skewed tree (linked list shape)
const skewed = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(3,
      new TreeNode(4))));
console.log(diameterOfBinaryTree(skewed)); // 3

// Two nodes
const twoNodes = new TreeNode(1, new TreeNode(2));
console.log(diameterOfBinaryTree(twoNodes)); // 1

Notice that a single node returns 0 because there are no edges. A skewed tree of n nodes has a diameter of n-1, since the longest path runs from the root to the deepest leaf.

Iterative Alternative

While the recursive solution is elegant, deeply nested trees can cause stack overflow errors in JavaScript. For production environments handling untrusted or extremely deep trees, an iterative post-order traversal using an explicit stack is safer.

function diameterIterative(root) {
  if (root === null) return 0;

  const stack = [[root, false]];
  const heights = new Map();
  let maxDiameter = 0;

  while (stack.length > 0) {
    const [node, visited] = stack.pop();

    if (visited) {
      const leftHeight = node.left ? heights.get(node.left) : 0;
      const rightHeight = node.right ? heights.get(node.right) : 0;

      maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
      heights.set(node, 1 + Math.max(leftHeight, rightHeight));
    } else {
      stack.push([node, true]);
      if (node.right) stack.push([node.right, false]);
      if (node.left) stack.push([node.left, false]);
    }
  }

  return maxDiameter;
}

This version uses a Map to store computed heights and a boolean flag to distinguish between the first visit (push children) and the second visit (compute height). It achieves the same O(n) time complexity while avoiding recursion limits.

Best Practices

When implementing this solution in real projects or interviews, keep the following best practices in mind:

• Prefer the recursive DFS solution for clarity unless tree depth is a concern. It is easier to read, test, and maintain.
• Use a closure or class field for the maximum diameter variable rather than passing it through return values. This keeps the code clean and avoids confusing return semantics.
• Always test edge cases: empty trees, single nodes, skewed trees, and balanced trees should all be covered by your test suite.
• Document the distinction between height and diameter. A common bug is returning the diameter instead of the height from the helper function, which breaks the recursion.
• Consider memory usage for very large trees. The iterative approach uses a Map that grows with the number of nodes, which may be significant.
• Validate input types if the function is part of a public API. Ensure the input is either null or a valid TreeNode instance.

Performance Comparison

To appreciate the difference between the brute-force and optimized approaches, consider a balanced tree with 10,000 nodes. The brute-force method makes repeated height calculations, resulting in roughly 50 million operations. The optimized DFS visits each node once, performing around 10,000 operations. That is a 5,000x improvement, demonstrating why algorithmic optimization matters.

// Quick benchmark sketch
const largeTree = buildBalancedTree(10000);

console.time('brute');
diameterBruteForce(largeTree);
console.timeEnd('brute');

console.time('optimized');
diameterOfBinaryTree(largeTree);
console.timeEnd('optimized');

In practice, the optimized version completes in milliseconds while the brute-force version can take seconds or even longer on sufficiently large inputs.

Conclusion

The diameter of a binary tree is a deceptively simple problem that rewards careful thinking about tree structure and recursion. By combining height computation with diameter tracking in a single DFS pass, we achieve an optimal O(n) solution that is both efficient and readable. Whether you choose the recursive or iterative approach depends on your specific constraints around tree depth and memory, but the core insight remains the same: every node is a potential pivot for the longest path, and the height of its subtrees tells us exactly how long that path could be. Mastering this pattern will serve you well in interviews and in any application that involves hierarchical data analysis.