105. Construct Binary Tree from Preorder and Inorder Traversal

Problem Link

Understand how preorder and inorder traversals define a binary tree uniquely.

In preorder traversal, the first element is always the root of the current subtree. In inorder traversal, all nodes to the left of the root belong to the left subtree, and all nodes to the right belong to the right subtree. Combining these two properties allows us to recursively reconstruct the tree.

Finding root node in inorder array directly would be expensive task making our solution \(O(n^2)\), instead we can maintain a Hashmap of val to index for inorder array to get the index in constant time.

To implement this approach recursively, we use a helper function that uses left and right pointer to specify the left and right subtree in inorder array. To point to start of preorder array, we use pre_idx, since this tells us the next root to create. To efficiently locate the root position in the inorder array, we use our hashmap. If the (left, right) is invalid, we return None. Otherwise, we take the next value from preorder as the root, find its position in inorder array, and recursively build the left and right subtrees using the corresponding inorder ranges.

Runtime Complexity

Time: \(O(n)\), since each node is processed once

Space: \(O(n)\) for the hashmap and recursion stack

PythonGo

class Solution:
    def _helper(self, left, right):
        if left > right:
            return

        val = self.preorder[self.pre_idx]
        self.pre_idx += 1
        mid = self.inorder[val]
        root = TreeNode(val)
        root.left = self._helper(left, mid-1)
        root.right = self._helper(mid+1, right)
        return root

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        self.inorder = {v: idx for idx, v in enumerate(inorder)}
        self.pre_idx = 0
        self.preorder = preorder
        return self._helper(0, len(inorder)-1)

func buildTree(preorder []int, inorder []int) *TreeNode {
    var helper func(left, right int) *TreeNode
    var preIdx int
    inorderMap := make(map[int]int)
    for idx, v := range inorder {
        inorderMap[v] = idx
    }
    helper = func(left, right int) *TreeNode {
        if left > right {
            return nil
        }

        val := preorder[preIdx]
        preIdx++
        mid := inorderMap[val]
        root := TreeNode{Val: val}
        root.Left = helper(left, mid-1)
        root.Right = helper(mid+1, right)
        return &root
    }

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

---