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

↓

Update max diameter if current diameter is larger

↓

Return height of current node = max(left height, right height) + 1

↓

Repeat for left and right child nodes recursively

↓

Final max diameter stored after full traversal

↓

End

The diameter is found by recursively computing heights of left and right subtrees at each node, updating the maximum diameter found as the sum of these heights.

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 max(left, right) + 1;
}

This code recursively calculates the height of each subtree and updates the diameter as the sum of left and right subtree heights at each node.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Diameter Update	Diameter Value	Visual State
1	Visit root	1	?	?	Calculate left and right heights	0	Root(1)
2	Visit left child	2	?	?	Calculate left and right heights	0	Root(1) -> Left(2)
3	Visit left-left child	4	0	0	Diameter = max(0,0+0)=0	0	Root(1) -> Left(2) -> Left(4)
4	Return height from node 4	4	0	0	-	-	Height=1 at node 4
5	Visit left-right child	5	0	0	Diameter = max(0,0+0)=0	0	Root(1) -> Left(2) -> Right(5)
6	Return height from node 5	5	0	0	-	-	Height=1 at node 5
7	Calculate height at node 2	2	1	1	Diameter = max(0,1+1)=2	2	Height=2 at node 2
8	Visit right child	3	?	?	Calculate left and right heights	2	Root(1) -> Right(3)
9	Visit right-left child	6	0	0	Diameter = max(2,0+0)=2	2	Root(1) -> Right(3) -> Left(6)
10	Return height from node 6	6	0	0	-	-	Height=1 at node 6
11	Visit right-right child	7	0	0	Diameter = max(2,0+0)=2	2	Root(1) -> Right(3) -> Right(7)
12	Return height from node 7	7	0	0	-	-	Height=1 at node 7
13	Calculate height at node 3	3	1	1	Diameter = max(2,1+1)=2	2	Height=2 at node 3
14	Calculate height at root node 1	1	2	2	Diameter = max(2,2+2)=4	4	Height=3 at root
15	End	-	-	-	-	4	Final diameter = 4

💡 All nodes visited, diameter updated to maximum sum of left and right subtree heights.

Variable Tracker

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

Key Moments - 3 Insights

Why do we add left and right subtree heights to update the diameter?

Because the diameter is the longest path between two nodes, which passes through the current node as the sum of left and right subtree heights (see Step 7 and Step 14 in execution_table).

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

Height is the longest path from current node down to a leaf, so we take the larger subtree height and add 1 for the current node (see Steps 4, 6, 7, 13, 14).

Why does the diameter update happen before returning height?

Because diameter depends on both left and right subtree heights at the current node, so we must compute and update diameter before returning height (see Steps 7 and 14).

Visual Quiz - 3 Questions

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

A 1

B 2

C 0

D 4

💡 Hint

Check the 'Diameter Value' column at Step 7 in execution_table.

At which step does the diameter first update to 4?

A Step 13

B Step 7

C Step 14

D Step 15

💡 Hint

Look at the 'Diameter Update' and 'Diameter Value' columns in execution_table for the largest update.

If the left subtree of root had height 1 instead of 2, how would the final diameter change?

A It would decrease by 1

B It would remain 4

C It would increase by 1

D It would become 2

💡 Hint

Diameter is sum of left and right heights at root (see Step 14 in execution_table).

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 of left and right subtrees
- Update max diameter during traversal
- Return height = max(left, right) + 1
- Final diameter stored in global variable

Full Transcript

The diameter of a binary tree is the longest path between any two nodes. We find it by visiting each node and calculating the height of its left and right subtrees. At each node, we add these heights to get the diameter passing through that node. We keep track of the maximum diameter found so far. The height returned from each node is one plus the maximum height of its subtrees. This process is done recursively starting from the root. The final diameter is the maximum sum of left and right subtree heights found during the traversal.