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.

Practice

1. What does the diameter of a binary tree represent?

easy

A. The longest path between any two nodes in the tree

B. The height of the tree

C. The number of leaf nodes

D. The total number of nodes in the tree

Solution

1. Step 1: Understand the diameter concept

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

2. Step 2: Differentiate from height and node count

   Height is the longest path from root to leaf, and node count is total nodes, both different from diameter.

3. Final Answer:

   The longest path between any two nodes in the tree -> Option A

4. Quick Check:

   Diameter = Longest path between nodes [OK]

Hint: Diameter is longest path, not just height or node count [OK]

Common Mistakes:

• Confusing diameter with tree height
• Thinking diameter counts nodes instead of edges
• Assuming diameter must pass through root

2. Which of the following JavaScript function signatures is correct for computing the diameter of a binary tree node?

easy

A. function diameterTree() {}

B. function diameter(root, tree) {}

C. function binaryTreeDiameter(node, root) {}

D. function diameterOfBinaryTree(root) {}

Solution

1. Step 1: Check common parameter naming

   The function usually takes the root node as input, so a single parameter named root is standard.

2. Step 2: Validate function signature correctness

   function diameterOfBinaryTree(root) {} uses a clear, single parameter 'root' and a descriptive function name, matching common practice.

3. Final Answer:

   function diameterOfBinaryTree(root) {} -> Option D

4. Quick Check:

   Correct function signature uses root parameter [OK]

Hint: Function usually takes root node as single parameter [OK]

Common Mistakes:

• Using multiple unrelated parameters
• Incorrect or unclear function names
• Missing parameters for the tree root

3. Given the following binary tree structure and code, what is the diameter of the tree?

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

const root = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(4),
    new TreeNode(5)
  ),
  new TreeNode(3)
);

function diameterOfBinaryTree(root) {
  let diameter = 0;
  function depth(node) {
    if (!node) return 0;
    const left = depth(node.left);
    const right = depth(node.right);
    diameter = Math.max(diameter, left + right);
    return Math.max(left, right) + 1;
  }
  depth(root);
  return diameter;
}

console.log(diameterOfBinaryTree(root));

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Analyze the tree structure

   The tree has root 1, left subtree with nodes 2,4,5 and right subtree with node 3. The longest path is from node 4 to node 3 through 2 and 1 (4->2->1->3), which has length 3 edges.

2. Step 2: Trace the code logic

   The code calculates diameter as max sum of left and right depths at each node. At node 2, left and right depths are 1 each, so diameter updates to 2. At root, left depth is 2, right depth is 1, so diameter updates to 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path edges = 3 [OK]

Hint: Diameter = max sum of left and right subtree depths [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring paths not passing through root
• Misreading tree structure

4. The following code attempts to compute the diameter of a binary tree but returns incorrect results. What is the bug?

function diameterOfBinaryTree(root) {
  let diameter = 0;
  function depth(node) {
    if (!node) return 0;
    const left = depth(node.left);
    const right = depth(node.right);
    diameter = Math.max(diameter, left * right);
    return Math.max(left, right) + 1;
  }
  depth(root);
  return diameter;
}

medium

A. Using multiplication instead of addition for diameter update

B. Returning max depth instead of sum of depths

C. Not handling null nodes correctly

D. Missing base case for leaf nodes

Solution

1. Step 1: Identify diameter update logic

   The code updates diameter using left * right, which multiplies depths instead of adding them.

2. Step 2: Correct diameter calculation

   Diameter should be updated with left + right, representing the longest path through the node.

3. Final Answer:

   Using multiplication instead of addition for diameter update -> Option A

4. Quick Check:

   Diameter update uses addition, not multiplication [OK]

Hint: Diameter update = left depth + right depth, not multiplication [OK]

Common Mistakes:

• Multiplying depths instead of adding
• Confusing depth return with diameter update
• Ignoring base case for null nodes

5. You want to find the diameter of a binary tree but also return the path nodes that form this diameter. Which approach correctly extends the diameter calculation to return the path?

hard

A. Use breadth-first search to find the longest path from root to any leaf

B. Only compute the height of the tree and return the nodes at the deepest level

C. Track left and right subtree depths and their paths; update diameter and store combined path when a longer diameter is found

D. Count total nodes and return all leaf nodes as the diameter path

Solution

1. Step 1: Understand diameter path requirements

   Diameter path is the longest path between any two nodes, so we must track paths from left and right subtrees.

2. Step 2: Extend depth function to track paths

   Along with depths, store paths for left and right subtrees. When diameter updates, combine these paths to form the diameter path.

3. Step 3: Reject incorrect approaches

   Height alone or BFS from root won't find longest path between any two nodes. Counting leaf nodes is unrelated.

4. Final Answer:

   Track left and right subtree depths and their paths; update diameter and store combined path when a longer diameter is found -> Option C

5. Quick Check:

   Track depths and paths to get diameter path [OK]

Hint: Store paths with depths; update when diameter increases [OK]

Common Mistakes:

• Only tracking height or BFS from root
• Ignoring path storage during recursion
• Assuming diameter path is always root to leaf