LeetCode Solutions Blog

Construct Binary Tree from Preorder and Inorder Traversal

Number: 105

Difficulty: Medium

Paid? No

Problem Description

Given the preorder and inorder traversal arrays of a binary tree, construct and return the binary tree. The preorder array represents the root-first traversal and the inorder array represents the left-root-right traversal.

Key Insights

Preorder traversal always starts with the root node.
Inorder traversal splits the tree into left subtree and right subtree based on the root.
A hash table (map/dictionary) can be used to quickly locate the index of the root in the inorder array.
Use recursion to construct left and right subtrees.

Space and Time Complexity

Time Complexity: O(n) since we process every node exactly once. Space Complexity: O(n) due to the recursion stack and the hash map used for inorder indices.

Solution

We solve the problem using a recursive divide-and-conquer approach. First, create a hash map to store each value's index in the inorder array for quick lookups. The preorder array always provides the current root. Use the inorder array to divide the tree into left and right subtrees. Recursively construct the subtrees by adjusting the preorder index and the boundaries of the inorder array. The algorithm leverages recursion and a hash map to achieve O(n) time complexity.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode:
        # Create a hashmap to store value->index for inorder traversal
        inorder_index = {value: idx for idx, value in enumerate(inorder)}
        
        # Recursive helper function to build the tree
        def helper(pre_start, in_left, in_right):
            # Base case: if there are no elements to construct subtree
            if in_left > in_right:
                return None
            
            # Pick up pre_start element as a root
            root_val = preorder[pre_start]
            root = TreeNode(root_val)
            
            # Get the inorder index of the root
            in_index = inorder_index[root_val]
            
            # Number of nodes in left subtree
            left_subtree_size = in_index - in_left
            
            # Recursively build the left subtree
            root.left = helper(pre_start + 1, in_left, in_index - 1)
            # Recursively build the right subtree
            root.right = helper(pre_start + left_subtree_size + 1, in_index + 1, in_right)
            
            return root
        
        # Initiate recursion from the start of preorder and full inorder range
        return helper(0, 0, len(inorder) - 1)