Diameter of Binary Tree in DSA Javascript - 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

↓

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

↓

Repeat for left and right child nodes recursively

↓

End when all nodes visited

↓

Final max diameter is result

We start at the root and recursively find the height of left and right subtrees. At each node, we calculate the diameter passing through it and update the maximum diameter found. We return the height to parent nodes to continue the process.

Execution Sample

DSA Javascript

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

This code calculates the diameter of a binary tree by recursively computing subtree heights and updating the maximum diameter found.

Execution Table

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

💡 All nodes visited, maxDiameter updated to 4, recursion ends.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 7	After Step 11	After Step 13	After Step 14	After Step 16	Final
maxDiameter	0	0	0	2	2	2	2	4	4
height(node 4)	?	1	1	1	1	1	1	1	1
height(node 5)	?	?	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 7)	?	?	?	?	?	1	1	1	1
height(node 3)	?	?	?	?	?	?	2	2	2
height(node 1)	?	?	?	?	?	?	?	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, which can pass through the current node connecting left and right subtrees. This is shown in execution_table rows 7, 14, and 16 where diameter through node is left height + right height.

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

Height is the longest path from the node down to a leaf. We add 1 for the current node itself. This is tracked in variable_tracker for each node's height after visiting children.

Why does maxDiameter update only when left + right is larger?

Because diameter is the longest path found so far. We update maxDiameter only if the current node's diameter (left + right) is greater, as seen in execution_table steps 7, 14, and 16.

Visual Quiz - 3 Questions

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

A 1

B 2

C 3

D 0

💡 Hint

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

At which step does maxDiameter first update to 2?

A Step 7

B Step 3

C Step 6

D Step 14

💡 Hint

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

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

A It would be left subtree height + 1

B It would be equal to left subtree height

C It would be left subtree height

D It would be 0

💡 Hint

Diameter through node is left height + right height. If right height is 0, diameter equals left height.

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 height = max(left, right) + 1
- Final max diameter is the answer

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. The diameter through a node is the sum of these heights. We keep track of the maximum diameter found so far. The height returned to parent nodes is the maximum of left and right heights plus one for the current node. This process repeats recursively until all nodes are visited. The final maximum diameter is returned as the result.