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

↓

Recurse for left child

↓

Recurse for right child

↓

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

↓

End when all nodes processed

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(TreeNode root) {
  int maxDiameter = 0;
  int Height(TreeNode node) {
    if (node == null) return 0;
    int left = Height(node.left);
    int 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.

Execution Table

Step	Operation	Current Node	Left Height	Right Height	Diameter Through Node	Max Diameter	Visual State
1	Start at root	1	?	?	?	0	1 / \ 2 3
2	Recurse left subtree	2	?	?	?	0	2 / \ 4 5
3	Recurse left subtree	4	0	0	0	0	4 (leaf)
4	Return height	4	0	0	0	0	Height=1
5	Recurse right subtree	5	0	0	0	0	5 (leaf)
6	Return height	5	0	0	0	0	Height=1
7	Calculate diameter	2	1	1	2	2	Node 2: left=1, right=1
8	Return height	2	1	1	2	2	Height=2
9	Recurse right subtree	3	?	?	?	2	3 / \ null 6
10	Recurse left subtree	null	0	0	0	2	null (empty)
11	Return height	null	0	0	0	2	Height=0
12	Recurse right subtree	6	0	0	0	2	6 (leaf)
13	Return height	6	0	0	0	2	Height=1
14	Calculate diameter	3	0	1	1	2	Node 3: left=0, right=1
15	Return height	3	0	1	1	2	Height=2
16	Calculate diameter	1	2	2	4	4	Root node: left=2, right=2
17	Return height	1	2	2	4	4	Height=3
18	End	null	-	-	-	4	Diameter found: 4

💡 All nodes processed, maxDiameter = 4

Variable Tracker

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

Key Moments - 3 Insights

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

Because the diameter through a node is the longest path passing through it, which equals left subtree height plus right subtree height (execution_table row 16 shows this).

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

Height is the longest path from node down to leaf, so we take the larger subtree height and add 1 for current node (see execution_table rows 8, 15, 17).

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

Because diameter is the longest path between any two nodes, so we keep track of the largest sum of left and right heights found so far (see execution_table rows 7 and 16).

Visual Quiz - 3 Questions

Look at the execution_table at step 16, what is the diameter through the root node?

A 3

B 4

C 2

D 5

💡 Hint

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

At which step does maxDiameter first update from 0 to a larger value?

A Step 3

B Step 13

C Step 7

D Step 16

💡 Hint

Look for the first step where 'Max Diameter' changes from 0 in execution_table.

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

A It would be equal to left height only

B It would be zero

C It would be sum of left and right heights as usual

D It would be one

💡 Hint

Refer to how diameter is calculated as left height + right height in execution_table and concept_flow.

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 answer

Full Transcript

The diameter of a binary tree is the longest path between any two nodes. To find it, we start at the root and recursively calculate the height of the left and right subtrees. At each node, we compute the diameter passing through it as the sum of left and right subtree heights. We keep track of the maximum diameter found so far. The height returned for each node is the maximum of left and right subtree heights plus one for the current node. After processing all nodes, the maximum diameter recorded is the diameter of the tree.

Practice

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

easy

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

B. The height of the tree from root to the deepest leaf

C. The total number of 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 the longest path from root to leaf, node count is total nodes, and leaf count is number of leaves, none of which define diameter.

3. Final Answer:

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

4. Quick Check:

   Diameter = longest path between nodes [OK]

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

Common Mistakes:

• Confusing diameter with tree height
• Thinking diameter counts nodes instead of edges
• Assuming diameter must pass through root

2. Which of the following C# method signatures is correct for a function that calculates the diameter of a binary tree node?

easy

A. Diameter public int(TreeNode root)

B. int Diameter(TreeNode root) void

C. public void Diameter(TreeNode root) int

D. public int Diameter(TreeNode root)

Solution

1. Step 1: Review C# method signature syntax

   In C#, method signature starts with access modifier, return type, method name, and parameters in parentheses.

2. Step 2: Check each option

   public int Diameter(TreeNode root) follows correct syntax: public int Diameter(TreeNode root). Others have incorrect order or missing parts.

3. Final Answer:

   public int Diameter(TreeNode root) -> Option D

4. Quick Check:

   Correct C# method syntax = public int Diameter(TreeNode root) [OK]

Hint: Method signature: access modifier + return type + name + parameters [OK]

Common Mistakes:

• Placing return type after parameters
• Omitting access modifier or return type
• Incorrect order of keywords

3. Given the following binary tree code snippet, what is the diameter of the tree?

class TreeNode {
  public int val;
  public TreeNode left, right;
  public TreeNode(int v) { val = v; }
}

// Tree structure:
//       1
//      / \
//     2   3
//    / 
//   4

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);

int diameter = CalculateDiameter(root); // Assume CalculateDiameter correctly implemented
Console.WriteLine(diameter);

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Visualize the tree and longest path

   The longest path is from node 4 to node 3: path length = edges 4->2->1->3 = 3 edges.

2. Step 2: Calculate diameter as number of edges

   Diameter counts edges, so longest path length is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path edges = 3 [OK]

Hint: Count edges on longest path, not nodes [OK]

Common Mistakes:

• Counting nodes instead of edges
• Assuming diameter passes through root only
• Ignoring one side of the tree

4. Identify the bug in this C# code snippet for calculating the diameter of a binary tree:

int maxDiameter = 0;
int Depth(TreeNode node) {
  if (node == null) return 0;
  int left = Depth(node.left);
  int right = Depth(node.right);
  maxDiameter = Math.Max(maxDiameter, left + right + 1);
  return Math.Max(left, right) + 1;
}

int Diameter(TreeNode root) {
  Depth(root);
  return maxDiameter;
}

medium

A. The base case should return 1 instead of 0

B. Diameter should be maxDiameter - 1 because diameter counts edges, not nodes

C. maxDiameter should be reset inside Depth method

D. Depth method should return left + right instead of max

Solution

1. Step 1: Understand diameter counting edges vs nodes

   The code adds left + right + 1 (nodes), but diameter counts edges, so subtract 1.

2. Step 2: Fix return value in Diameter method

   Return maxDiameter - 1 to convert node count to edge count for diameter.

3. Final Answer:

   Diameter should be maxDiameter - 1 because diameter counts edges, not nodes -> Option B

4. Quick Check:

   Diameter edges = nodes - 1 [OK]

Hint: Diameter = nodes on path - 1 (edges) [OK]

Common Mistakes:

• Returning maxDiameter directly without subtracting 1
• Changing base case return value incorrectly
• Resetting maxDiameter inside recursive calls

5. You want to find the diameter of a binary tree but also return the path nodes forming that diameter. Which approach correctly extends the diameter calculation?

hard

A. Calculate diameter first, then do a separate BFS to find the path

B. Store all paths from root to leaves and pick the longest one

C. Modify the recursive function to return both depth and path, updating max path when diameter increases

D. Use a queue to traverse level by level and count nodes

Solution

1. Step 1: Understand diameter and path relationship

   Diameter is longest path between any two nodes, so tracking path during recursion helps capture it.

2. Step 2: Extend recursion to return depth and path

   Modify recursive calls to return depth and path list; update max path when a longer diameter is found.

3. Step 3: Compare other options

   Calculate diameter first, then do a separate BFS to find the path is inefficient; C only finds longest root-to-leaf path, not diameter; D is unrelated to diameter.

4. Final Answer:

   Modify the recursive function to return both depth and path, updating max path when diameter increases -> Option C

5. Quick Check:

   Track depth and path together for diameter path [OK]

Hint: Return depth and path in recursion to track diameter path [OK]

Common Mistakes:

• Trying to find path after diameter without tracking during recursion
• Confusing longest root-to-leaf path with diameter
• Using BFS level order traversal which doesn't find diameter