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

↓

Calculate diameter in left subtree

↓

Calculate diameter in right subtree

↓

Compare diameters: max of (through current, left subtree, right subtree)

↓

Return max diameter

↓

Repeat for all nodes recursively

The diameter is found by checking each node's left and right subtree heights, summing them, and comparing with diameters of subtrees recursively.

Execution Sample

DSA Java

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

int diameter(TreeNode root) {
  // returns diameter of tree
  // Implementation needed here
}

This code calculates the diameter of a binary tree by recursively checking subtree heights and diameters.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Diameter Through Node	Max Diameter So Far	Visual State
1	Visit root	1	2	2	4	4	Node1 / \ N2 N3 / \ / \ N4 N5 N6 N7
2	Visit left child	2	1	1	2	4	Node2 / \ N4 N5
3	Visit left-left child	4	0	0	0	4	Node4 (leaf)
4	Visit left-right child	5	0	0	0	4	Node5 (leaf)
5	Visit right child	3	1	1	2	4	Node3 / \ N6 N7
6	Visit right-left child	6	0	0	0	4	Node6 (leaf)
7	Visit right-right child	7	0	0	0	4	Node7 (leaf)
8	Calculate diameter at root	1	2	2	4	4	Final diameter = 4
9	Return max diameter	root	-	-	-	4	Diameter of tree is 4
10	End	-	-	-	-	-	Traversal complete

💡 All nodes visited, maximum diameter found as 4

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 7	Final
Current Node	1	4	5	6	7	-
Left Height	0	0	0	0	0	2
Right Height	0	0	0	0	0	2
Diameter Through Node	0	0	0	0	0	4
Max Diameter So Far	0	0	0	0	0	4

Key Moments - 3 Insights

Why do we add left height and right height to get diameter through 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 their heights gives that path length (see Step 8 in execution_table).

Why do we compare diameter through current node with diameters of left and right subtrees?

Because the longest path might not pass through current node; it could be entirely in left or right subtree. So we take max of all three (Step 8).

What is the height of a leaf node and why?

Height of leaf node is 0 because it has no children (Steps 3,4,6,7 show left and right heights as 0).

Visual Quiz - 3 Questions

Look at the execution_table at Step 8, what is the diameter through the root node?

A 2

B 0

C 4

D 3

💡 Hint

Check the 'Diameter Through Node' column at Step 8 in execution_table.

At which step does the traversal visit the right-right child node?

A Step 6

B Step 7

C Step 5

D Step 4

💡 Hint

Look at the 'Node Visited' column in execution_table to find node 7.

If the left subtree height of the root was 3 instead of 2, how would the diameter through the root change?

A It would become 5

B It would become 6

C It would stay 4

D It would become 3

💡 Hint

Diameter through node = left height + right height (see Step 8).

Concept Snapshot

Diameter of Binary Tree:
- Diameter = longest path between any two nodes
- For each node: diameter = left height + right height
- Recursively compute left/right subtree heights and diameters
- Result = max(diameter through node, left subtree diameter, right subtree diameter)
- Height of leaf node = 0
- Use post-order traversal to compute heights and diameters

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 passing through that node is the sum of these heights. We also find the maximum diameter in the left and right subtrees. The overall diameter is the maximum of these three values. Leaf nodes have height zero because they have no children. We use a post-order traversal to compute heights and diameters from bottom up. This method ensures we check all possible longest paths in the tree.

Practice

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

easy

A. The number of leaf nodes in the tree

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

C. The height of the tree

D. The total number of nodes in the tree

Solution

1. Step 1: Understand the diameter definition

   The diameter is the longest path between any two nodes, which may or may not pass through the root.

2. Step 2: Differentiate from other tree properties

   Height is the longest path from root to leaf, leaf count is number of leaves, total nodes is size, none of which define diameter.

3. Final Answer:

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

4. Quick Check:

   Diameter = Longest path between nodes [OK]

Hint: Diameter is longest path between any two nodes [OK]

Common Mistakes:

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

2. Which of the following Java method signatures correctly represents a recursive function to find the diameter of a binary tree node?

easy

A. public int diameter(int root)

B. public void diameter(TreeNode root)

C. public String diameter(TreeNode root)

D. public int diameter(TreeNode root)

Solution

1. Step 1: Identify correct parameter type

   The method must accept a TreeNode object representing the root of the tree or subtree.

2. Step 2: Identify correct return type

   Diameter is a number (int), so return type should be int, not void or String.

3. Final Answer:

   public int diameter(TreeNode root) -> Option D

4. Quick Check:

   Method returns int and takes TreeNode [OK]

Hint: Diameter method returns int and takes TreeNode [OK]

Common Mistakes:

• Using void return type for diameter
• Passing int instead of TreeNode
• Returning String instead of int

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

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

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

// Diameter calculation code omitted for brevity

medium

A. 2

B. 5

C. 3

D. 4

Solution

1. Step 1: Visualize the tree structure

   The tree has root 1, left child 2 with children 4 and 5, and right child 3.

2. Step 2: Find longest path between any two nodes

   Longest path is from node 4 to node 3 via 2 and 1: path 4->2->1->3 = 3 edges, diameter = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Count edges on longest path between two nodes [OK]

Common Mistakes:

• Counting nodes instead of edges or vice versa
• Ignoring paths not passing through root
• Miscounting edges in path

4. Identify the bug in this diameter calculation method and select the fix:

int diameter = 0;
int height(TreeNode root) {
  if (root == null) return 0;
  int left = height(root.left);
  int right = height(root.right);
  diameter = Math.max(diameter, left + right);
  return Math.max(left, right);
}

medium

A. Return Math.max(left, right) + 1 instead of Math.max(left, right)

B. Initialize diameter inside height method

C. Use diameter = Math.min(diameter, left + right)

D. Return left + right instead of Math.max(left, right)

Solution

1. Step 1: Understand height calculation

   Height of a node is 1 plus max height of its children, so must add +1.

2. Step 2: Identify bug in return statement

   Current code returns max(left, right) without +1, so height is underestimated.

3. Final Answer:

   Return Math.max(left, right) + 1 instead of Math.max(left, right) -> Option A

4. Quick Check:

   Height = max child height + 1 [OK]

Hint: Height adds 1 to max child height [OK]

Common Mistakes:

• Forgetting to add +1 in height return
• Using min instead of max for diameter update
• Returning sum of left and right as height

5. You want to find the diameter of a binary tree but also print the nodes on the longest path. Which approach is best?

hard

A. Modify the diameter function to store and return the longest path nodes along with diameter

B. Calculate diameter first, then do a separate BFS to find longest path nodes

C. Use only height function and print nodes at max height

D. Count leaf nodes and assume longest path is between two leaves

Solution

1. Step 1: Understand diameter and path relationship

   Diameter is longest path length; to print nodes, we must track path during diameter calculation.

2. Step 2: Choose approach that combines diameter and path tracking

   Modifying diameter function to store nodes on longest path is efficient and direct.

3. Final Answer:

   Modify the diameter function to store and return the longest path nodes along with diameter -> Option A

4. Quick Check:

   Track path during diameter calc for nodes [OK]

Hint: Track nodes while computing diameter for path [OK]

Common Mistakes:

• Running BFS separately wastes time
• Assuming height equals diameter path
• Counting leaves without path tracking