Diameter of Binary Tree in DSA Javascript

Mental Model

The diameter is the longest path between any two nodes in the tree, which may or may not pass through the root.

Analogy: Imagine a network of roads connecting towns (nodes). The diameter is the longest direct route you can travel between any two towns without repeating roads.

      1
     / \
    2   3
   / \
  4   5

Diameter is the longest path between two nodes, for example 4 -> 2 -> 1 -> 3.

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5

Goal: Find the longest path between any two nodes in the tree

Step 1: Start at node 4, calculate height (0) and diameter (0)

Node 4: height=0, diameter=0

Why: Leaf nodes have height 0 and no path through them

Step 2: Calculate height and diameter for node 5 similarly

Node 5: height=0, diameter=0

Why: Leaf nodes have height 0 and no path through them

Step 3: At node 2, height = max(height of 4, height of 5) + 1 = 1; diameter = max(diameter of 4, diameter of 5, height of 4 + height of 5 + 2) = 2

Node 2: height=1, diameter=2 (path 4 -> 2 -> 5)

Why: Diameter through node 2 is longest path between its children plus 2 edges

Step 4: At node 3, height=0, diameter=0 (leaf node)

Node 3: height=0, diameter=0

Why: Node 3 has no children

Step 5: At root node 1, height = max(height of 2, height of 3) + 1 = 2; diameter = max(diameter of 2, diameter of 3, height of 2 + height of 3 + 2) = 3

Node 1: height=2, diameter=3 (path 4 -> 2 -> 1 -> 3)

Why: Longest path goes through root connecting deepest nodes in left and right subtrees

Result:

Diameter of the tree is 3 edges: 4 -> 2 -> 1 -> 3

Annotated Code

DSA Javascript

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

function diameterOfBinaryTree(root) {
  let maxDiameter = 0;

  function height(node) {
    if (node === null) return -1; // base case: height of empty node is -1

    const leftHeight = height(node.left); // get height of left subtree
    const rightHeight = height(node.right); // get height of right subtree

    // diameter through this node is leftHeight + rightHeight + 2 edges
    const diameterThroughNode = leftHeight + rightHeight + 2;
    if (diameterThroughNode > maxDiameter) {
      maxDiameter = diameterThroughNode; // update max diameter if bigger
    }

    return Math.max(leftHeight, rightHeight) + 1; // height of current node
  }

  height(root); // start recursion from root
  return maxDiameter;
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3)
);
console.log(diameterOfBinaryTree(root));

if (node === null) return -1;

base case: empty node has height -1 to count edges correctly

const leftHeight = height(node.left);

recursively get height of left subtree

const rightHeight = height(node.right);

recursively get height of right subtree

const diameterThroughNode = leftHeight + rightHeight + 2;

calculate diameter passing through current node

if (diameterThroughNode > maxDiameter) { maxDiameter = diameterThroughNode; }

update global max diameter if current is larger

return Math.max(leftHeight, rightHeight) + 1;

return height of current node for parent's calculation

Output

3

Complexity Analysis

Time: O(n) because each node is visited once during height calculation

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach might compute height repeatedly causing O(n^2) time; this method computes height and diameter in one pass

Edge Cases

Empty tree (root is null)

Returns diameter 0 as there are no edges

DSA Javascript

if (node === null) return -1;

Single node tree

Diameter is 0 because no edges exist

DSA Javascript

if (node === null) return -1;

Tree with only left or only right children

Diameter equals the height of the longest path down the tree

DSA Javascript

const diameterThroughNode = leftHeight + rightHeight + 2;

When to Use This Pattern

When asked for the longest path between any two nodes in a tree, use the diameter pattern by combining heights of left and right subtrees at each node.

Common Mistakes

Mistake: Returning height as 0 for null nodes instead of -1, causing off-by-one errors in diameter calculation
Fix: Return -1 for null nodes so edge count matches path length correctly

Mistake: Calculating diameter separately from height causing repeated work and O(n^2) time
Fix: Calculate diameter during height recursion to keep O(n) time

Summary

Finds the longest path between any two nodes in a binary tree measured in edges.

Use when you need the maximum distance between any two nodes, not just root to leaf.

The diameter at a node equals left subtree height plus right subtree height plus two edges.