Diameter of Binary Tree in DSA Typescript

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 tree as a network of roads connecting cities. The diameter is the longest possible trip you can take between two cities without repeating roads.

      1
     / \
    2   3
   / \   \
  4   5   6

Here, arrows show parent to child connections.

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3; 2 -> 4, 5; 3 -> null, 6

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

Step 1: Calculate height of node 4 (leaf)

Node 4 height = 0

Why: Leaf nodes have height zero, base for recursion

Step 2: Calculate height of node 5 (leaf)

Node 5 height = 0

Why: Leaf nodes have height zero, base for recursion

Step 3: Calculate height of node 2 using children 4 and 5

Node 2 height = max(0,0) + 1 = 1
Diameter through 2 = 0 + 0 + 2 = 2

Why: Height is max child height + 1; diameter through node is sum of left and right heights plus 2 edges

Step 4: Calculate height of node 6 (leaf)

Node 6 height = 0

Why: Leaf nodes have height zero

Step 5: Calculate height of node 3 using right child 6

Node 3 height = max(-1,0) + 1 = 1
Diameter through 3 = -1 + 0 + 2 = 1

Why: Left child is null (-1 height), right child height 0, so height is 1

Step 6: Calculate height of root node 1 using children 2 and 3

Node 1 height = max(1,1) + 1 = 2
Diameter through 1 = 1 + 1 + 2 = 4

Why: Diameter through root is sum of left and right heights plus 2 edges

Step 7: Compare all diameters found and select maximum

Max diameter = 4

Why: Longest path found is diameter

Result:

Diameter path length = 4 edges (path: 4 -> 2 -> 1 -> 3 -> 6)

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function diameterOfBinaryTree(root: TreeNode | null): number {
  let maxDiameter = 0;

  function height(node: TreeNode | null): number {
    if (node === null) return -1; // base case: empty subtree

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

    // diameter through current node is leftHeight + rightHeight + 2 edges
    const diameterThroughNode = leftHeight + rightHeight + 2;

    if (diameterThroughNode > maxDiameter) {
      maxDiameter = diameterThroughNode; // update max diameter if larger
    }

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

  height(root);
  return maxDiameter;
}

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

if (node === null) return -1; // base case: empty subtree

return -1 for null to count edges correctly

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

recursively find left subtree height

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

recursively find right subtree height

const diameterThroughNode = leftHeight + rightHeight + 2;

calculate diameter passing through current node

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

update max diameter if current is larger

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

return height of current node for parent's calculation

Output

4

Complexity Analysis

Time: O(n) because we visit each node once to compute heights and diameters

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

vs Alternative: Naive approach recalculates heights repeatedly causing O(n^2) time; this optimized method uses post-order traversal to compute heights once

Edge Cases

Empty tree (root is null)

Returns diameter 0 because no nodes exist

DSA Typescript

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

Single node tree

Diameter is 0 since no edges exist

DSA Typescript

const diameterThroughNode = leftHeight + rightHeight + 2;

Skewed tree (all nodes only on one side)

Diameter equals number of edges in the longest path (height of tree)

DSA Typescript

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

When to Use This Pattern

When asked for the longest path between any two nodes in a tree, use the diameter pattern by combining subtree heights to find max path length.

Common Mistakes

Mistake: Returning node count instead of edge count for diameter
Fix: Return -1 for null nodes so height counts edges, not nodes

Mistake: Recomputing heights multiple times causing slow code
Fix: Use a single post-order traversal to compute heights and update diameter simultaneously

Summary

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

Use when you need the maximum distance between two nodes in a tree structure.

The diameter is the largest sum of left and right subtree heights plus two edges at any node.

Practice

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

easy

A. The height of the tree

B. The number of nodes in the tree

C. The number of leaf nodes in the tree

D. The length of the longest path between any two nodes in the tree

Solution

1. Step 1: Understand the diameter definition

   The diameter is the longest path between any two nodes, not just from root to leaf.

2. Step 2: Differentiate from other tree properties

   Height is longest root-to-leaf path, number of nodes counts all nodes, leaves count only leaf nodes.

3. Final Answer:

   The length of the longest path between any two nodes in the tree -> Option D

4. Quick Check:

   Diameter = longest path between nodes [OK]

Hint: Diameter is longest path between any two nodes, not just height [OK]

Common Mistakes:

• Confusing diameter with tree height
• Thinking diameter counts nodes instead of edges
• Assuming diameter is from root only

2. Which TypeScript function signature correctly represents a function to compute the diameter of a binary tree node?

easy

A. function diameter(root: TreeNode | null): number

B. function diameter(root: number): TreeNode

C. function diameter(root: TreeNode): void

D. function diameter(): number

Solution

1. Step 1: Identify input and output types

   The function takes a TreeNode or null and returns a number representing diameter length.

2. Step 2: Match correct signature

   function diameter(root: TreeNode | null): number matches input type TreeNode|null and returns number, others mismatch input/output.

3. Final Answer:

   function diameter(root: TreeNode | null): number -> Option A

4. Quick Check:

   Input: TreeNode|null, Output: number [OK]

Hint: Diameter function inputs root node, returns number length [OK]

Common Mistakes:

• Using wrong input type like number instead of TreeNode
• Returning void instead of number
• Missing null option for empty tree

3. What is the diameter of the following binary tree?

    1
   / \
  2   3
 / 
4  

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Identify longest path in tree

   Longest path is from node 4 to node 3 passing through 2 and 1, length 3 edges.

2. Step 2: Count edges in longest path

   Path 4 -> 2 -> 1 -> 3 has 3 edges, so diameter is 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path edges = 3 [OK]

Hint: Count edges on longest path between any two nodes [OK]

Common Mistakes:

• Counting nodes instead of edges
• Choosing height instead of diameter
• Ignoring path through root

4. Given this TypeScript code snippet to compute diameter, what is the error?

function diameter(root: TreeNode | null): number {
  let maxDiameter = 0;
  function depth(node: TreeNode | null): number {
    if (!node) return 0;
    const left = depth(node.left);
    const right = depth(node.right);
    maxDiameter = Math.max(maxDiameter, left + right + 1);
    return Math.max(left, right) + 1;
  }
  depth(root);
  return maxDiameter;
}

medium

A. Diameter counts nodes, should count edges (subtract 1)

B. Missing base case for null node

C. Returns depth instead of diameter

D. maxDiameter is not updated inside depth function

Solution

1. Step 1: Analyze diameter calculation

   maxDiameter updates with left + right + 1, counting nodes on path.

2. Step 2: Correct diameter definition

   Diameter is number of edges, so subtract 1 from node count to get edges.

3. Final Answer:

   Diameter counts nodes, should count edges (subtract 1) -> Option A

4. Quick Check:

   Diameter edges = nodes - 1 [OK]

Hint: Diameter = nodes on path minus 1 for edges [OK]

Common Mistakes:

• Confusing nodes count with edges count
• Forgetting to subtract 1 for edges
• Incorrect base case handling

5. How would you modify the diameter function to also return the actual longest path nodes in TypeScript?

hard

A. Use BFS to find diameter and path separately after diameter calculation

B. Return only diameter number, path cannot be found during recursion

C. Track and store nodes on longest path during recursion, return path array with diameter

D. Store only leaf nodes and reconstruct path after diameter is found

Solution

1. Step 1: Understand diameter path tracking

   During recursion, keep track of nodes on left and right depths to build longest path.

2. Step 2: Modify function to store and return path

   Update maxDiameter and store nodes forming longest path, return both diameter and path array.

3. Final Answer:

   Track and store nodes on longest path during recursion, return path array with diameter -> Option C

4. Quick Check:

   Store nodes during recursion to get path [OK]

Hint: Store nodes on longest path during recursion to return path [OK]

Common Mistakes:

• Assuming path cannot be found during recursion
• Trying BFS after diameter calculation only
• Only storing leaf nodes misses full path