LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal Solution in Python Explained

Problem Statement

In LeetCode 105, you’re given two integer arrays: preorder (root, left, right) and inorder (left, root, right) traversals of a binary tree with unique values. Your task is to construct the binary tree and return its root. This contrasts with depth measurement like LeetCode 104: Maximum Depth of Binary Tree, focusing on tree reconstruction from traversal data.

Constraints

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• Values are unique
• Arrays represent a valid tree

Example

Let’s see some cases:

Copy codeInput: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
      3
     / \
    9  20
       / \
      15  7
Explanation: Preorder gives root (3), Inorder splits left (9) and right (15,20,7).

Copy codeInput: preorder = [1], inorder = [1]
Output: [1]
Explanation: Single node tree.

Copy codeInput: preorder = [1,2], inorder = [2,1]
Output: [1,2]
Explanation: Root 1, left 2.

These examples show we’re reconstructing a tree from traversals.

Understanding the Problem

How do you solve LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal in Python? Take preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]. Preorder starts with the root (3), and inorder splits at 3 into left (9) and right (15,20,7). Recursively build subtrees using these splits. This isn’t a zigzag traversal like LeetCode 103: Binary Tree Zigzag Level Order Traversal; it’s about tree construction. We’ll use: 1. Recursive Construction with Hash Map: O(n) time, O(n) space—our best solution. 2. Recursive without Hash Map: O(n²) time, O(h) space—an alternative.

Let’s dive into the best solution.

Best Solution: Recursive Construction with Hash Map Approach

Explanation

Recursive Construction with Hash Map uses preorder’s first element as the root and inorder to determine left and right subtrees. A hash map stores inorder indices for O(1) lookup, enabling efficient splitting. Recursively build the tree by adjusting indices. This is the best solution due to its O(n) time complexity, leveraging the hash map to avoid linear searches, making it both efficient and clear.

For preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]:

• Root: 3 (preorder[0]), inorder index 1.
• Left: 9 (inorder[0:1]), Right: 15,20,7 (inorder[2:5]).
• Recurse on subarrays.

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Goal: Return [3,9,20,null,null,15,7].

• Start: inorder_map = {9:0, 3:1, 15:2, 20:3, 7:4}, build(0, 0, 5).
• Step 1: Root = preorder[0] = 3, in_idx = 1.
• Left size = 1 - 0 = 1.
• Left: build(1, 0, 1).
• Root = 9, in_idx = 0, size = 0.
• Left: None, Right: None.
• Return 9.
• Right: build(2, 2, 5).
• Root = 20, in_idx = 3, size = 1.
• Left: build(3, 2, 3) → 15.
• Right: build(4, 4, 5) → 7.
• Return 20->15->7.
• Return 3->9->20.
• Finish: [3,9,20,null,null,15,7].

Example 2: preorder = [1], inorder = [1]

Goal: Return [1].

• Start: inorder_map = {1:0}, build(0, 0, 1).
• Step 1: Root = 1, in_idx = 0, size = 0.
• Left: None, Right: None.
• Finish: Return [1].

Example 3: preorder = [1,2], inorder = [2,1]

Goal: Return [1,2].

• Start: inorder_map = {2:0, 1:1}, build(0, 0, 2).
• Step 1: Root = 1, in_idx = 1, size = 1.
• Left: build(1, 0, 1) → 2.
• Right: None.
• Finish: Return [1,2].

How the Code Works (Recursive Construction with Hash Map) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode:
    # Line 1: Create hash map for inorder indices
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    # Maps values to indices (e.g., {9:0, 3:1, 15:2, 20:3, 7:4})
    # Enables O(1) lookup of root position

    # Line 2: Define recursive builder function
    def build(pre_start: int, in_start: int, in_end: int) -> TreeNode:
        # pre_start = preorder start index, in_start = inorder start, in_end = inorder end
        # e.g., (0, 0, 5) for full tree

        # Line 3: Base case - no nodes to process
        if in_start >= in_end:
            # If range is empty (e.g., 0 >= 0), return None
            return None

        # Line 4: Get root value from preorder
        root_val = preorder[pre_start]
        # First element is root (e.g., 3 at pre_start=0)

        # Line 5: Create root node
        root = TreeNode(root_val)
        # New node with root value (e.g., 3)

        # Line 6: Find root index in inorder
        root_idx = inorder_map[root_val]
        # O(1) lookup (e.g., 3 → 1)

        # Line 7: Calculate left subtree size
        left_size = root_idx - in_start
        # Number of nodes in left subtree (e.g., 1 - 0 = 1)

        # Line 8: Recursively build left subtree
        root.left = build(pre_start + 1, in_start, root_idx)
        # Preorder: next index (e.g., 1), Inorder: start to root_idx (e.g., 0 to 1)
        # e.g., builds node 9

        # Line 9: Recursively build right subtree
        root.right = build(pre_start + left_size + 1, root_idx + 1, in_end)
        # Preorder: skip left_size (e.g., 2), Inorder: root_idx+1 to end (e.g., 2 to 5)
        # e.g., builds node 20 with 15, 7

        # Line 10: Return constructed subtree
        return root
        # Returns root of current subtree (e.g., 3->9->20)

    # Line 11: Start construction
    return build(0, 0, len(preorder))
    # Initiates with full range (e.g., 0, 0, 5)
    # Returns root of constructed tree

This detailed breakdown clarifies how recursive construction with a hash map efficiently builds the tree.

Alternative: Recursive without Hash Map Approach

Explanation

Recursive without Hash Map finds the root in preorder, searches for it in inorder to split left and right subtrees, and builds recursively without a hash map. It’s a straightforward alternative but slower due to O(n) searches in inorder.

For [3,9,20,15,7], [9,3,15,20,7]:

• Root 3, split at index 1.
• Left: 9, Right: 20,15,7.
• Recurse similarly.

Step-by-Step Example (Alternative)

For [3,9,20,15,7], [9,3,15,20,7]:

• Step 1: Root = 3, find 3 in inorder (index 1).
• Left: [9], Right: [20,15,7].
• Step 2: Left = 9, no children.
• Step 3: Right = 20, split [15,20,7] → 15, 7.
• Finish: [3,9,20,null,null,15,7].

How the Code Works (Recursive without Hash Map)

Copy codedef buildTreeNoHash(preorder: list[int], inorder: list[int]) -> TreeNode:
    if not preorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    root_idx = inorder.index(root_val)
    root.left = buildTreeNoHash(preorder[1:root_idx + 1], inorder[:root_idx])
    root.right = buildTreeNoHash(preorder[root_idx + 1:], inorder[root_idx + 1:])
    return root

Complexity

• Recursive Construction with Hash Map:
• Time: O(n) – hash map enables O(1) lookups.
• Space: O(n) – hash map and recursion stack.
• Recursive without Hash Map:
• Time: O(n²) – O(n) search per node.
• Space: O(h) – recursion stack, h = height.

Efficiency Notes

Recursive Construction with Hash Map is the best solution with O(n) time and O(n) space, optimizing lookups—Recursive without Hash Map is O(n²) due to linear searches, making it a simpler but less efficient alternative.

Key Insights

• Preorder: Root first.
• Inorder: Splits subtrees.
• Hash Map: Speeds up indexing.

Additional Example

For preorder = [1,2,4,3], inorder = [4,2,1,3]:

• Goal: [1,2,3,4].
• Hash Map: Builds 1->2->4 (left), 3 (right).

Edge Cases

• Single Node: [1], [1] → [1].
• Left Skewed: [1,2,3], [3,2,1] → [1,2,3].
• Empty: [], [] → None.

Both solutions handle these well.

Final Thoughts

LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal in Python is a compelling tree-building challenge. The Recursive Construction with Hash Map solution excels with its efficiency and clarity, while Recursive without Hash Map offers a simpler approach. Want more? Try LeetCode 94: Binary Tree Inorder Traversal for traversal basics or LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal for a related task. Ready to practice? Solve LeetCode 105 on LeetCode with [3,9,20,15,7] and [9,3,15,20,7], aiming for [3,9,20,null,null,15,7]—test your skills now!