Tree: Depth-First Search - Diameter of Binary Tree
What is the time complexity of the brute force recursive approach that computes the diameter of a binary tree by calculating the height at each node separately?
What is the time complexity of the brute force recursive approach that computes the diameter of a binary tree by calculating the height at each node separately?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Solution:
Step 1: Analyze the height function calls.
Height is called for each node, and each call traverses its subtree, leading to repeated traversals.Step 2: Calculate total complexity.
For each of the n nodes, height is computed which can take O(n) in worst case, resulting in O(n^2) total time.Final Answer:
Option C -> Option CQuick Check:
Repeated height computations cause quadratic time [OK]
Quick Trick: Repeated height calls cause O(n^2) time, not O(n) [OK]
Common Mistakes:
MISTAKES- Assuming height calls are O(1)
- Confusing recursion stack space with time
- Thinking it's O(n log n) due to balanced tree
Trap Explanation:
PITFALL- Candidates often think height is cached or constant time, underestimating repeated subtree traversals.
Interviewer Note:
CONTEXT- Tests understanding of recursion cost and repeated computations in naive solutions.
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