Why Diameter of Binary Tree in DSA Typescript?

The Big Idea

Discover how to find the longest path in a tree without checking every possibility by hand!

The Scenario

Imagine you have a family tree drawn on paper, and you want to find the longest path between any two family members. Doing this by looking at every possible path manually is confusing and takes a lot of time.

The Problem

Manually checking every path in a tree is slow and easy to mess up. You might miss some paths or repeat checking the same parts again and again, making it frustrating and error-prone.

The Solution

The Diameter of a Binary Tree concept helps us find the longest path between any two nodes quickly by using a smart way to check each part of the tree only once. This saves time and avoids mistakes.

Before vs After

✗ Before

function findLongestPath(root) {
  // Check all paths manually, very slow
  // Hard to track and repeat work
}

✓ After

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

What It Enables

This concept lets you quickly find the longest connection in any tree structure, unlocking better understanding and faster decisions.

Real Life Example

In a company's organizational chart, finding the longest chain of command helps understand communication flow and potential delays.

Key Takeaways

Manual path checking in trees is slow and error-prone.

Diameter calculation uses a smart depth-first approach to find the longest path efficiently.

This helps analyze tree structures quickly in many real-world cases.

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