Diameter of Binary Tree in DSA C - Execution Trace

Concept Flow - Diameter of Binary Tree

Start at root node

↓

Compute left subtree height

↓

Compute right subtree height

↓

Calculate diameter through current node = left height + right height

↓

Compare with max diameter so far

↓

Recurse to left child

↓

Recurse to right child

↓

Return max diameter found

Calculate height of left and right subtrees at each node, update max diameter as sum of these heights, then recurse to children.

Execution Sample

DSA C

int diameter = 0;

int height(TreeNode* node) {
  if (!node) return 0;
  int left = height(node->left);
  int right = height(node->right);
  diameter = max(diameter, left + right);
  return 1 + max(left, right);
}

Recursively compute height of subtrees, update diameter as max sum of left and right heights.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Diameter Updated	Visual State
1	Visit root (1)	1	?	?	No	Root(1)
2	Visit left child (2)	2	?	?	No	1 -> 2
3	Visit left child of 2 (4)	4	0	0	No	1 -> 2 -> 4
4	Return height 1 for node 4	4	0	0	No	Leaf 4 height=1
5	Visit right child of 2 (5)	5	0	0	No	1 -> 2 -> 5
6	Return height 1 for node 5	5	0	0	No	Leaf 5 height=1
7	Calculate diameter at node 2	2	1	1	Updated to 2	Diameter=2 at node 2
8	Return height 2 for node 2	2	1	1	Diameter=2	Height=2 at node 2
9	Visit right child (3)	3	?	?	No	1 -> 3
10	Visit left child of 3 (null)	null	0	?	No	Null left child
11	Visit right child of 3 (6)	6	0	0	No	1 -> 3 -> 6
12	Return height 1 for node 6	6	0	0	No	Leaf 6 height=1
13	Calculate diameter at node 3	3	0	1	No change	Diameter=2 still
14	Return height 2 for node 3	3	0	1	Diameter=2	Height=2 at node 3
15	Calculate diameter at root (1)	1	2	2	Updated to 4	Diameter=4 at root
16	Return height 3 for root (1)	1	2	2	Diameter=4	Height=3 at root
17	End recursion	null	-	-	-	Final diameter=4

💡 All nodes visited, recursion ends with diameter = 4

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 8	After Step 12	After Step 13	After Step 14	After Step 15	Final
diameter	0	0	0	2	2	2	2	2	4	4
height(node 4)	?	1	1	1	1	1	1	1	1	1
height(node 5)	?	?	1	1	1	1	1	1	1	1
height(node 2)	?	?	?	?	2	2	2	2	2	2
height(node 6)	?	?	?	?	?	1	1	1	1	1
height(node 3)	?	?	?	?	?	?	2	2	2	2
height(root 1)	?	?	?	?	?	?	?	?	3	3

Key Moments - 3 Insights

Why do we add left height and right height to update diameter?

Because diameter is the longest path between two nodes, which passes through current node as left height + right height (see step 7 and 15 in execution_table).

Why do we return 1 + max(left, right) as height?

Height counts current node plus the taller subtree height, so we add 1 to max(left, right) (see steps 4, 6, 8, 12, 14, 16).

Why does diameter update only sometimes?

Diameter updates only if current sum of left and right heights is greater than previous max (see step 7 updates diameter to 2, step 15 updates to 4).

Visual Quiz - 3 Questions

Look at the execution_table, what is the diameter after visiting node 2?

A 2

B 1

C 0

D 4

💡 Hint

Check step 7 where diameter updates after node 2 is visited.

At which step does the diameter update to its final value?

A Step 7

B Step 15

C Step 13

D Step 4

💡 Hint

Look for the step where diameter changes from 2 to 4 in execution_table.

If node 3 had a left child with height 2, how would diameter at root change?

A It would remain 4

B It would decrease

C It would increase above 4

D It would become 2

💡 Hint

Diameter at root is sum of left and right heights; increasing right height increases diameter (see step 15).

Concept Snapshot

Diameter of Binary Tree:
- Diameter = longest path between any two nodes
- At each node, diameter = left height + right height
- Use recursion to get heights
- Update max diameter during recursion
- Return height = 1 + max(left, right)
- Final diameter is max found

Full Transcript

The diameter of a binary tree is the longest path between any two nodes. We find it by recursively calculating the height of left and right subtrees at each node. At each node, we update the diameter as the sum of left and right subtree heights if it is larger than the current maximum. The height returned for each node is 1 plus the maximum height of its children. This process continues until all nodes are visited, and the maximum diameter found is the answer.

Practice

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

easy

A. The total number of nodes in the tree

B. The height of the tree

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

D. The number of leaf 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 longest path from root to leaf, leaf count is number of leaves, total nodes is size. Diameter is distinct.

3. Final Answer:

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

4. Quick Check:

   Diameter = longest path length [OK]

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

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of edges
• Assuming diameter always passes through root

2. Which of the following C function signatures is correct for a helper function that returns the height of a binary tree node for diameter calculation?

easy

A. int height(struct Node* root);

B. void height(struct Node root);

C. int height(Node root);

D. int height(struct Node root);

Solution

1. Step 1: Check parameter type for tree node

   In C, tree nodes are passed as pointers to struct Node, so parameter should be struct Node* root.

2. Step 2: Check return type and parameter correctness

   Height returns int, so return type int is correct. Passing pointer is correct, not struct by value.

3. Final Answer:

   int height(struct Node* root); -> Option A

4. Quick Check:

   Pointer parameter and int return type [OK]

Hint: Use pointer to struct Node for tree nodes in C [OK]

Common Mistakes:

• Passing struct Node by value instead of pointer
• Using void return type instead of int
• Missing struct keyword in parameter

3. What is the output of the following C code snippet that calculates the diameter of a binary tree?

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

int height(struct Node* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int diameter(struct Node* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  int leftDiameter = diameter(root->left);
  int rightDiameter = diameter(root->right);
  int maxDiameter = leftHeight + rightHeight + 1;
  if (leftDiameter > maxDiameter) maxDiameter = leftDiameter;
  if (rightDiameter > maxDiameter) maxDiameter = rightDiameter;
  return maxDiameter;
}

int main() {
  struct Node n1 = {1, NULL, NULL};
  struct Node n2 = {2, NULL, NULL};
  struct Node n3 = {3, &n1, &n2};
  printf("%d", diameter(&n3));
  return 0;
}

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Analyze tree structure

   Root n3 has two children n1 and n2, both leaves. Height of left and right subtree is 1 each.

2. Step 2: Calculate diameter

   Diameter = max of (leftHeight + rightHeight + 1, leftDiameter, rightDiameter) = max(1+1+1, 1, 1) = 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Diameter = 3 nodes in longest path [OK]

Hint: Diameter = max(leftHeight + rightHeight + 1, leftDiameter, rightDiameter) [OK]

Common Mistakes:

• Confusing diameter with height
• Forgetting to add 1 for root node in diameter
• Using height instead of diameter in comparisons

4. Identify the bug in this C function that attempts to compute the diameter of a binary tree:

int diameter(struct Node* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  int leftDiameter = diameter(root->left);
  int rightDiameter = diameter(root->right);
  int maxDiameter = leftHeight + rightHeight;
  if (leftDiameter > maxDiameter) maxDiameter = leftDiameter;
  if (rightDiameter > maxDiameter) maxDiameter = rightDiameter;
  return maxDiameter;
}

medium

A. height function is not called correctly

B. maxDiameter should be leftHeight + rightHeight + 1

C. Function should return height, not diameter

D. Missing base case for leaf nodes

Solution

1. Step 1: Check diameter calculation formula

   Diameter includes edges between nodes, so it should add 1 for the root node connecting left and right paths.

2. Step 2: Identify missing +1 in maxDiameter

   Current code misses +1, so maxDiameter undercounts by 1.

3. Final Answer:

   maxDiameter should be leftHeight + rightHeight + 1 -> Option B

4. Quick Check:

   Diameter = leftHeight + rightHeight + 1 [OK]

Hint: Add 1 to sum of heights for diameter at root [OK]

Common Mistakes:

• Omitting +1 in diameter calculation
• Confusing height and diameter returns
• Not handling null root base case

5. Given a binary tree where each node stores an integer, how would you modify the diameter calculation to find the diameter based on the sum of node values along the longest path instead of the number of nodes?

hard

A. Change height function to return max sum of node values from root to leaf, and update diameter to sum left and right max sums plus root's value

B. Use the existing diameter function but multiply the result by the root node's value

C. Replace all node values with 1 and then calculate diameter normally

D. Calculate diameter normally and then add all node values in the tree separately

Solution

1. Step 1: Modify height to return max sum path

   Instead of counting nodes, height returns max sum of node values from root to leaf recursively.

2. Step 2: Update diameter to sum left and right max sums plus root value

   Diameter becomes max of leftDiameter, rightDiameter, and leftSum + rightSum + root's value.

3. Final Answer:

   Change height function to return max sum of node values from root to leaf, and update diameter to sum left and right max sums plus root's value -> Option A

4. Quick Check:

   Diameter by sum = max path sum through root [OK]

Hint: Use max sum path instead of node count for diameter sum [OK]

Common Mistakes:

• Multiplying diameter by root value incorrectly
• Ignoring node values in diameter calculation
• Adding all node values separately instead of path sums