Tree: Depth-First Search - Diameter of Binary Tree
The following code attempts to compute the diameter of a binary tree using an optimized recursive approach. Identify the line containing the subtle bug that causes incorrect diameter calculation.
The following code attempts to compute the diameter of a binary tree using an optimized recursive approach. Identify the line containing the subtle bug that causes incorrect diameter calculation.
medium🐞 Bug Identification Q14 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand diameter definition counts edges, not nodes.
The diameter is the number of edges on the longest path, so it should be left + right, not left + right + 1.Step 2: Identify the bug line.
Line 9 adds 1 incorrectly, causing diameter to be off by one.Final Answer:
Option B -> Option BQuick Check:
Diameter must be sum of left and right heights (edges), not nodes [OK]
Quick Trick: Diameter counts edges = left + right, not +1 [OK]
Common Mistakes:
MISTAKES- Adding 1 to diameter sum
- Not using nonlocal for diameter
- Returning wrong height value
Trap Explanation:
PITFALL- Adding 1 to diameter sum looks like height calculation but is incorrect for diameter edges.
Interviewer Note:
CONTEXT- Checks if candidate distinguishes between node count and edge count in diameter.
Master "Diameter of Binary Tree" in Tree: Depth-First Search
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Tree: Depth-First Search Quizzes