Diameter of Binary Tree in DSA Go - Execution Trace

Concept Flow - Diameter of Binary Tree

Start at root node

↓

Compute left subtree height

↓

Compute right subtree height

↓

Calculate diameter at this node = left height + right height

↓

Update max diameter if current is larger

↓

Return height = max(left height, right height) + 1

↓

Repeat for left and right child nodes recursively

↓

Final max diameter is the answer

We recursively find the height of left and right subtrees at each node, update the maximum diameter found, and return the height to parent nodes.

Execution Sample

DSA Go

func diameterOfBinaryTree(root *TreeNode) int {
  maxDiameter := 0
  var height func(node *TreeNode) int
  height = func(node *TreeNode) int {
    if node == nil { return 0 }
    left := height(node.Left)
    right := height(node.Right)
    if left + right > maxDiameter { maxDiameter = left + right }
    if left > right {
      return left + 1
    }
    return right + 1
  }
  height(root)
  return maxDiameter
}

This code calculates the diameter of a binary tree by recursively computing subtree heights and tracking the maximum sum of left and right heights.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Diameter at Node	Max Diameter	Return Height	Visual State
1	Visit node	1 (root)	?	?	?	0	?	[1]
2	Visit left child	2	?	?	?	0	?	[1 -> 2]
3	Visit left child	4	0	0	0	0	1	[1 -> 2 -> 4]
4	Return from node	4	0	0	0	0	1	[1 -> 2 -> 4]
5	Visit right child	5	0	0	0	0	1	[1 -> 2 -> 5]
6	Return from node	5	0	0	0	0	1	[1 -> 2 -> 5]
7	Calculate diameter	2	1	1	2	2	2	[1 -> 2 -> 4,5]
8	Return from node	2	1	1	2	2	2	[1 -> 2 -> 4,5]
9	Visit right child	3	?	?	?	2	?	[1 -> 3]
10	Visit left child	6	0	0	0	2	1	[1 -> 3 -> 6]
11	Return from node	6	0	0	0	2	1	[1 -> 3 -> 6]
12	Visit right child	7	0	0	0	2	1	[1 -> 3 -> 7]
13	Return from node	7	0	0	0	2	1	[1 -> 3 -> 7]
14	Calculate diameter	3	1	1	2	2	2	[1 -> 3 -> 6,7]
15	Return from node	3	1	1	2	2	2	[1 -> 3 -> 6,7]
16	Calculate diameter	1	2	2	4	4	3	[1 -> 2,3 -> 4,5,6,7]
17	Return from node	1	2	2	4	4	3	[1 -> 2,3 -> 4,5,6,7]
18	End	-	-	-	-	4	-	[Final diameter = 4]

💡 Traversal complete, max diameter found is 4 (longest path between two nodes).

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 7	After Step 11	After Step 14	After Step 16	Final
maxDiameter	0	0	0	2	2	2	4	4
left (height)	?	1	1	1	1	1	2	2
right (height)	?	?	1	1	1	1	2	2
return height	?	1	1	2	1	2	3	3

Key Moments - 3 Insights

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

Because the diameter is the longest path through that node, which is the sum of the longest path down the left subtree and the longest path down the right subtree. See execution_table rows 7, 14, and 16 where diameter at node is left height + right height.

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

Height is the longest path from the node down to a leaf. We take the larger height of left or right subtree and add 1 for the current node. This is shown in execution_table rows 4, 6, 8, 11, 13, 15, and 17.

How does maxDiameter get updated during recursion?

At each node, we check if left height + right height is greater than current maxDiameter and update it. This happens in rows 7, 14, and 16 where maxDiameter changes from 0 to 2 and then to 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the diameter at node 2?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'Diameter at Node' column in row 7 of execution_table.

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

A Step 7

B Step 3

C Step 14

D Step 16

💡 Hint

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

If the tree had no right subtree, how would maxDiameter change at the root?

A It would be zero

B It would be left height + right height (which is zero)

C It would be equal to left height

D It would be one

💡 Hint

Recall diameter at node is left height + right height; if right height is zero, diameter equals left height + 0.

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 subtrees
- Update max diameter during traversal
- Return height = max(left, right) + 1
- Final max diameter is answer

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. The diameter at a node is the sum of left and right subtree heights. We keep track of the maximum diameter found during traversal. The height returned to parent nodes is the maximum of left and right heights plus one for the current node. This process continues until all nodes are visited, and the maximum diameter found is returned as the result.