How to Solve: Construct Binary Tree from Preorder and Inorder Traversal

How to Solve: Construct Binary Tree from Preorder and Inorder Traversal

(Complete Guide for FAANG-Level Interviews)

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you prove you can recursively decompose problems, optimize with hash maps, and handle edge cases like a senior engineer."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Binary Tree Traversals (Preorder, Inorder, Postorder) – Know the order of node visits. 2. Hash Maps (Dictionaries) – For O(1) lookups of node positions. 3. Recursive Problem Decomposition – Breaking problems into smaller subproblems (divide and conquer).

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

(Repeatable mental checklist for every problem of this type.)

1. Identify the Root

2. The first element in preorder is always the root of the tree (or subtree).

3. Locate the Root in Inorder

4. Find the root’s position in inorder (use a hash map for O(1) lookup).
5. All elements left of root in inorder = left subtree.

6. All elements right of root in inorder = right subtree.

7. Recursively Build Subtrees

8. Left Subtree:
   • Preorder: Next left_size elements after root.
   • Inorder: Elements left of root.

9. Right Subtree:

   • Preorder: Remaining elements after left subtree.
   • Inorder: Elements right of root.

10. Optimize with Bounds (Avoid Array Slicing)

11. Instead of slicing arrays (O(n) space), use pointers (pre_start, in_start, in_end) to track ranges.

12. Base Case

13. If in_start > in_end, return None (no subtree exists).

14. Edge Cases

15. Empty input → Return None.
16. Duplicate values → Problem is unsolvable (assume unique values).

✅ WORKED EXAMPLES

Example 1 – Basic

Problem: Given preorder = [3,9,20,15,7], inorder = [9,3,15,20,7], construct the binary tree.

Thought Process: 1. Root = 3 (first in preorder). 2. In inorder, 3 is at index 1 → Left subtree: [9], Right subtree: [15,20,7]. 3. Left Subtree:
- Preorder: [9] (next element after root).
- Inorder: [9] → Root = 9, no children. 4. Right Subtree:
- Preorder: [20,15,7].
- Inorder: [15,20,7] → Root = 20, Left = [15], Right = [7]. 5. Recurse:
- Left of 20: [15] → Leaf node.
- Right of 20: [7] → Leaf node.

Code (Python):

class TreeNode:

    def __init__(self, val=0, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

def buildTree(preorder, inorder):

    inorder_map = {val: idx for idx, val in enumerate(inorder)}


    def helper(pre_start, in_start, in_end):

        if in_start > in_end:

            return None


        root_val = preorder[pre_start]

        root = TreeNode(root_val)

        root_pos = inorder_map[root_val]


        left_size = root_pos - in_start

        root.left = helper(pre_start + 1, in_start, root_pos - 1)

        root.right = helper(pre_start + left_size + 1, root_pos + 1, in_end)


        return root


    return helper(0, 0, len(inorder) - 1)

Time Complexity: O(n) (each node processed once). Space Complexity: O(n) (hash map + recursion stack).

Why This Works: - Preorder gives the root first, inorder splits left/right subtrees. - Hash map avoids O(n) searches for root positions.

Example 2 – Medium (With Duplicates?)

Problem: What if inorder has duplicates? (e.g., preorder = [1,1], inorder = [1,1])

Thought Process: - Problem is unsolvable if duplicates exist (ambiguous root position). - Assumption: All values are unique (standard interview constraint).

Code Adjustment: - Add a check at the start:

if len(set(inorder)) != len(inorder):

    return None  # or raise ValueError

Why This Works: - Without unique values, we cannot determine the root’s position in inorder.

Example 3 – Hard (Follow-Up: Postorder + Inorder)

Problem: Given postorder and inorder, construct the tree.

Thought Process: 1. Root = last element in postorder (not first). 2. Inorder splits left/right subtrees (same as before). 3. Recurse:
- Left subtree: post_start to post_start + left_size - 1.
- Right subtree: post_start + left_size to post_end - 1.

Code (Python):

def buildTree(postorder, inorder):

    inorder_map = {val: idx for idx, val in enumerate(inorder)}


    def helper(post_end, in_start, in_end):

        if in_start > in_end:

            return None


        root_val = postorder[post_end]

        root = TreeNode(root_val)

        root_pos = inorder_map[root_val]


        left_size = root_pos - in_start

        root.left = helper(post_end - (in_end - root_pos) - 1, in_start, root_pos - 1)

        root.right = helper(post_end - 1, root_pos + 1, in_end)


        return root


    return helper(len(postorder) - 1, 0, len(inorder) - 1)

Time Complexity: O(n). Space Complexity: O(n).

Why This Works: - Postorder’s root is at the end, but the logic for splitting subtrees remains the same.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s the playbook to crush this problem in your interview: 1. Root is first in preorder—grab it, then find its position in inorder. 2. Split inorder into left and right subtrees around the root. 3. Recurse on the left and right, using pointers to avoid slicing arrays. 4. Optimize with a hash map for O(1) root lookups. 5. Edge cases: Empty input, duplicates (clarify with interviewer).

This pattern shows up in Google, Meta, and Amazon interviews—practice it until you can code it in your sleep. Good luck!

? Final Notes

• Practice Variations: Try postorder + inorder, or preorder + postorder (harder, requires unique values).
• Whiteboard Tip: Draw the tree first, then map traversals to nodes.
• Time Yourself: Aim for 15 minutes from problem statement to working code.

You’ve got this! ?