Bird
Raised Fist0

What is the time complexity of the optimized iterative approach using a stack and a hash map to build a binary tree from preorder and inorder traversals of length n?

medium🪤 Complexity Trap Q13 of Q15
Tree: Depth-First Search - Construct Tree from Preorder and Inorder
What is the time complexity of the optimized iterative approach using a stack and a hash map to build a binary tree from preorder and inorder traversals of length n?
AO(n^2) due to nested loops scanning preorder and inorder arrays
BO(n log n) due to hash map lookups for inorder indices
CO(n) because each node is pushed and popped at most once from the stack
DO(n) but with O(n^2) auxiliary space for recursion stack
Step-by-Step Solution

  1. Step 1: Analyze main loops

    The algorithm iterates preorder once, pushing and popping nodes from stack at most once each.

  2. Step 2: Consider hash map lookups

    Hash map lookups for inorder indices are O(1) each, so no extra log factor.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Each node processed once with O(1) operations [OK]
Quick Trick: Each node pushed and popped once; hash map lookups O(1) [OK]
Common Mistakes:
MISTAKES
  • Assuming nested loops cause O(n^2)
  • Confusing hash map lookup cost
  • Counting recursion stack space in iterative approach
Trap Explanation:
PITFALL
  • O(n^2) looks plausible if one forgets that stack operations are amortized O(1) per node.
Interviewer Note:
CONTEXT
  • Checks understanding of amortized complexity and hash map usage.
Master "Construct Tree from Preorder and Inorder" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes
Balanced Binary Tree - Balanced Binary Tree - Quiz 10hard Binary Tree Maximum Path Sum - Binary Tree Maximum Path Sum - Quiz 7medium Binary Tree Postorder Traversal - Binary Tree Postorder Traversal - Quiz 3easy Construct Tree from Inorder and Postorder - Construct Tree from Inorder and Postorder - Quiz 1easy Count Complete Tree Nodes - Count Complete Tree Nodes - Quiz 1easy Invert Binary Tree - Invert Binary Tree - Quiz 6medium Path Sum - Path Sum - Quiz 10hard Path Sum III (Any Path) - Path Sum III (Any Path) - Quiz 1easy Symmetric Tree (DFS Approach) - Symmetric Tree (DFS Approach) - Quiz 2easy Symmetric Tree (DFS Approach) - Symmetric Tree (DFS Approach) - Quiz 12easy