Diameter of Binary Tree in DSA Typescript - Build from Scratch

Diameter of Binary Tree

📖 Scenario: You are working on a network system where each node represents a server. The longest path between any two servers in the network is important to understand the maximum delay in communication.This network is represented as a binary tree where each node can have up to two connections (left and right child nodes).

🎯 Goal: Calculate the diameter of the binary tree, which is the length of the longest path between any two nodes in the tree.You will build a TypeScript program that defines the tree, sets up a helper variable, implements the diameter calculation, and finally prints the diameter.

📋 What You'll Learn

Define a binary tree node class with val, left, and right properties

Create a sample binary tree with exactly 5 nodes with given values

Use a helper variable to track the maximum diameter found during traversal

Implement a recursive function to calculate the diameter of the binary tree

Print the final diameter value

💡 Why This Matters

🌍 Real World

Understanding the longest path in a network or tree structure helps in optimizing communication delays and resource allocation.

💼 Career

This concept is useful for software engineers working on network design, distributed systems, and performance optimization.

1

Define the Binary Tree and Create the Sample Tree

Define a class called TreeNode with a constructor that takes a number val and initializes left and right as null. Then create a binary tree with root node value 1, left child 2, right child 3, left child of node 2 as 4, and right child of node 2 as 5.

DSA Typescript

// Define TreeNode class and create the binary tree
// Your code here

Hint

Start by defining the TreeNode class with val, left, and right. Then create the nodes and link them as described.

2

Add a Helper Variable to Track Maximum Diameter

Create a variable called maxDiameter and initialize it to 0. This will keep track of the longest path found during the tree traversal.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

// Create maxDiameter variable and set to 0
// Your code here

Hint

Just create a variable maxDiameter and set it to zero before starting the diameter calculation.

3

Implement the Diameter Calculation Function

Write a recursive function called depth that takes a TreeNode | null parameter called node. It should return the maximum depth of the subtree rooted at node. Inside the function, calculate the left and right depths by calling depth recursively. Update maxDiameter with the sum of left and right depths if it is larger than the current maxDiameter. Return the maximum of left and right depths plus one.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

let maxDiameter = 0;

// Write the depth function below
// Your code here

Hint

Use recursion to find the depth of left and right subtrees. Update maxDiameter with the sum of these depths if it is larger. Return the max depth plus one.

4

Print the Diameter of the Binary Tree

Write a console.log statement to print the value of maxDiameter.

DSA Typescript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;

    constructor(val: number) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

let maxDiameter = 0;

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

depth(root);

// Print the maxDiameter
// Your code here

Hint

Use console.log(maxDiameter) to display the diameter after the recursive calls.

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