DSAPrep
MediumTrees

Construct Binary Tree From Preorder And Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder and inorder consist of unique values.
  • Each value of inorder also appears in preorder.
  • preorder is guaranteed to be the preorder traversal of the tree.
  • inorder is guaranteed to be the inorder traversal of the tree.
View original on LeetCode ↗

preorder’s first element is always the current subtree’s root. Finding that same value in inorder splits the remaining values into “everything in the left subtree” (values before it) and “everything in the right subtree” (values after it) — exactly the information needed to recurse. The only question is how cheaply that split can be located and passed down.

Recursive with Slicing + Linear Search

Time O(n^2)Space O(n^2)

Take preorder[0] as the root, find it in inorder with .index(), then slice both arrays into left/right pieces and recurse.

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 | None:
        if not preorder:
            return None
        root_val = preorder[0]
        root = TreeNode(root_val)
        mid = inorder.index(root_val)
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
        return root

Complexity: .index() scans up to n elements at every one of n calls → O(n^2) time worst case, and slicing copies arrays at every level → O(n^2) space for all the slice copies combined.

Hashmap Index + Pointer (no slicing)

OptimalTime O(n)Space O(n)

Two changes remove the quadratic behavior: a hashmap from value to its index in inorder turns the “find the root” step into O(1), and a single shared pointer into preorder (rather than slicing it) tracks which element is “next” without copying arrays. Only the inorder range shrinks per call, via plain index bounds.

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        index_of = {val: i for i, val in enumerate(inorder)}
        self.pre_idx = 0


        def build(left: int, right: int) -> TreeNode | None:
            if left > right:
                return None
            root_val = preorder[self.pre_idx]
            self.pre_idx += 1
            root = TreeNode(root_val)
            mid = index_of[root_val]
            root.left = build(left, mid - 1)
            root.right = build(mid + 1, right)
            return root


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

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

3
1 / 5
result

preorder[0]=3 is the root. In inorder, 3 splits into left=[9] and right=[15,20,7].

Complexity: each call does O(1) hashmap lookup work and the shared pointer visits each preorder element exactly once → O(n) time. The hashmap plus the recursion stack (which reaches O(n) depth on a skewed tree) → O(n) space.