Tree: Depth-First Search - Diameter of Binary Tree
Given the following optimized recursive code snippet to compute the diameter of a binary tree, what is the returned diameter for the tree: root = [1,2,3,4,5] (where 4 and 5 are children of 2)?
Given the following optimized recursive code snippet to compute the diameter of a binary tree, what is the returned diameter for the tree: root = [1,2,3,4,5] (where 4 and 5 are children of 2)?
easy🧾 Code Trace Q3 of Q15
Step-by-Step Solution
Solution:
Step 1: Trace height and diameter at node 2
Node 4 and 5 have height 1 each, so diameter at node 2 is 1+1=2.Step 2: Trace diameter at root
Left subtree height=2 (from node 2), right subtree height=1 (node 3), diameter=max(2,2+1=3)=3.Final Answer:
Option A -> Option AQuick Check:
Diameter is edges count on longest path -> 3 [OK]
Quick Trick: Diameter = max sum of left and right subtree heights
Common Mistakes:
MISTAKES- Counting nodes instead of edges
- Forgetting to update diameter at each node
Trap Explanation:
PITFALL- Candidates often confuse diameter as number of nodes, not edges, leading to off-by-one errors.
Interviewer Note:
CONTEXT- Tests ability to mentally execute optimized recursive diameter code
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