Tree: Depth-First Search - Construct Tree from Preorder and Inorder
What is the space complexity of the recursive approach with a hash map for inorder indices when building a binary tree from preorder and inorder traversals of size n?
What is the space complexity of the recursive approach with a hash map for inorder indices when building a binary tree from preorder and inorder traversals of size n?
medium🪤 Complexity Trap Q6 of Q15
Step-by-Step Solution
Solution:
Step 1: Account for hash map space
Hash map stores n inorder indices, requiring O(n) space.Step 2: Account for recursion stack
In worst case (skewed tree), recursion stack depth is O(n).Final Answer:
Option D -> Option DQuick Check:
Hash map + recursion stack sum to O(n) [OK]
Quick Trick: Recursion stack + hash map dominate space [OK]
Common Mistakes:
MISTAKES- Ignoring recursion stack space
Trap Explanation:
PITFALL- Candidates often forget recursion stack space, assuming constant or log space.
Interviewer Note:
CONTEXT- Tests understanding of auxiliary space in recursion
Master "Construct Tree from Preorder and Inorder" 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