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.