Diameter of Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Diameter of Binary Tree

Start at root node

↓

Calculate left subtree height

↓

Calculate right subtree height

↓

Calculate diameter through current node = left height + right height

↓

Update max diameter if current diameter is larger

↓

Recursively repeat for left child

↓

Recursively repeat for right child

↓

Return max diameter found

We find the height of left and right subtrees at each node, calculate diameter through that node, update max diameter, and recurse for all nodes.

Execution Sample

DSA Typescript

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

Calculates the diameter of a binary tree by recursively computing subtree heights and updating max diameter.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Diameter Through Node	Max Diameter	Visual Tree State
1	Visit node	1 (root)	?	?	?	0	1 / \ 2 3
2	Visit node	2 (left child)	?	?	?	0	1 / \ 2 3
3	Visit node	4 (left child of 2)	0	0	0	0	1 / \ 2 3 / 4
4	Return height	4	0	0	0	0	1 / \ 2 3 / 4
5	Visit node	5 (right child of 2)	0	0	0	0	1 / \ 2 3 / \ 4 5
6	Return height	5	0	0	0	0	1 / \ 2 3 / \ 4 5
7	Calculate heights	2	1	1	2	2	1 / \ 2 3 / \ 4 5
8	Return height	2	1	1	2	2	1 / \ 2 3 / \ 4 5
9	Visit node	3 (right child)	?	?	?	2	1 / \ 2 3 / \ 4 5
10	Visit node	6 (left child of 3)	0	0	0	2	1 / \ 2 3 / \ 4 5 / 6
11	Return height	6	0	0	0	2	1 / \ 2 3 / \ 4 5 / 6
12	Visit node	7 (right child of 3)	0	0	0	2	1 / \ 2 3 / \ 4 5 / \ 6 7
13	Return height	7	0	0	0	2	1 / \ 2 3 / \ 4 5 / \ 6 7
14	Calculate heights	3	1	1	2	2	1 / \ 2 3 / \ 4 5 / \ 6 7
15	Return height	3	1	1	2	2	1 / \ 2 3 / \ 4 5 / \ 6 7
16	Calculate heights	1 (root)	2	2	4	4	1 / \ 2 3 / \ 4 5 / \ 6 7
17	Return height	1 (root)	2	2	4	4	1 / \ 2 3 / \ 4 5 / \ 6 7
18	End	-	-	-	-	4	Final max diameter is 4

💡 All nodes visited, max diameter updated to 4, recursion ends

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 11	After Step 13	After Step 15	After Step 17	Final
maxDiameter	0	0	0	2	2	2	2	4	4
height(4)	N/A	1	1	1	1	1	1	1	1
height(5)	N/A	N/A	1	1	1	1	1	1	1
height(2)	N/A	N/A	N/A	2	2	2	2	2	2
height(6)	N/A	N/A	N/A	N/A	1	1	1	1	1
height(7)	N/A	N/A	N/A	N/A	N/A	1	1	1	1
height(3)	N/A	N/A	N/A	N/A	N/A	N/A	2	2	2
height(1)	N/A	N/A	N/A	N/A	N/A	N/A	N/A	3	3

Key Moments - 3 Insights

Why do we add left height and right height to get diameter at a node?

Because diameter is the longest path between two nodes, passing through current node means path goes down left subtree and right subtree, so sum of left and right heights gives that path length (see step 7 and 14).

Why do we update maxDiameter inside the height function?

Because at each node we calculate diameter through it and compare with maxDiameter so far, updating maxDiameter ensures we keep track of the largest diameter found during recursion (see steps 7, 14, and 16).

Why does height return 1 + max(left, right)?

Height counts edges down to leaf plus current node, so 1 for current node plus the taller subtree height below it (see steps 8, 15, 17).

Visual Quiz - 3 Questions

Look at the execution table at step 16, what is the diameter through the root node?

A 4

B 2

C 3

D 0

💡 Hint

Check the 'Diameter Through Node' column at step 16 in the execution_table.

At which step does maxDiameter first update from 0 to 2?

A Step 14

B Step 4

C Step 7

D Step 16

💡 Hint

Look at the 'Max Diameter' column in execution_table rows to find when it changes from 0 to 2.

If node 5 had a left child, how would maxDiameter change at step 7?

A It would stay the same

B It would increase

C It would decrease

D It would become zero

💡 Hint

Adding a child increases subtree height, which increases diameter through node (see how diameter is left + right heights).

Concept Snapshot

Diameter of Binary Tree:
- Diameter = longest path between any two nodes
- At each node, diameter = left subtree height + right subtree height
- Use recursion to get heights and update max diameter
- Return max diameter after full traversal
- Height(node) = 1 + max(height(left), height(right))

Full Transcript

The diameter of a binary tree is the longest path between any two nodes. To find it, we visit each node and calculate the height of its left and right subtrees. The diameter through that node is the sum of these two heights. We keep track of the maximum diameter found so far. We use a recursive function to compute heights and update the maximum diameter. Finally, we return the maximum diameter after visiting all nodes. The height of a node is 1 plus the maximum height of its children. This approach ensures we consider all possible paths in the tree.

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