Q64: Construct Tree from Preorder & Inorder Traversal. - DSA Patterns (Multi-Lang)

In Simple Words: First element of preorder is always root. Find root's position in inorder using a Hash Map: elements to the left form left subtree, elements to the right form right subtree.

Time: $O(N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
    in_map = {val: i for i, val in enumerate(inorder)}
    pre_idx = 0
    def build(l, r):
        nonlocal pre_idx
        if l > r: return None
        root_val = preorder[pre_idx]
        pre_idx += 1
        root = TreeNode(root_val)
        mid = in_map[root_val]
        root.left = build(l, mid - 1)
        root.right = build(mid + 1, r)
        return root
    return build(0, len(inorder) - 1)