MediumArrayHash TableDivide and ConquerTreeBinary Tree

Construct Binary Tree from Preorder and Inorder Traversal

1 approach, code in every language

You are given two integer arrays, preorder and inorder. The preorder array lists the node values of a binary tree in the order they are visited during a preorder traversal (root, then left subtree, then right subtree), while inorder lists them in inorder traversal order (left subtree, then root, then right subtree).

Every value in the tree is unique. Reconstruct the original binary tree and return its root.

Example 1

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

Output: [3,9,20,null,null,15,7]

3 is the root because it comes first in preorder. In inorder it sits at index 1, so [9] forms the left subtree and [15,20,7] forms the right subtree, which recursion rebuilds.

Example 2

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

Output: [-1]

A single value yields a tree that contains only the root node.

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.

Recursion with an Inorder Index Map

Use the first preorder value as the root, locate it in inorder to split the array, and recurse with a moving preorder pointer.

Loading animation…

Intuition

Preorder visits the root first, so the very first unused preorder value is always the root of the current subtree. In inorder, that root sits between its left subtree (to the left) and its right subtree (to the right). Once we know the root's position in inorder, every value to its left belongs to the left subtree and every value to its right belongs to the right subtree. Scanning inorder for the root on each call would cost O(n) per node, so we precompute a hash map from value to inorder index for O(1) lookups. Advancing a single shared preorder pointer as we build lets us hand out roots in exactly the order preorder demands.

Algorithm walkthrough

1Build a hash map that maps each inorder value to its index, and initialize a preorder pointer at 0.
2Define a recursive helper that receives the inorder bounds [left, right] of the current subtree.
3If left exceeds right the range is empty, so return null.
4Take the value at the preorder pointer as the root and advance the pointer, then look up its inorder index mid in the map.
5Recurse on [left, mid - 1] to build the left subtree, then on [mid + 1, right] for the right subtree so the order matches how preorder consumes roots.
6Return the assembled root; the top-level call spans the entire inorder range.

Implementation

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        idx = {v: i for i, v in enumerate(inorder)}
        self.pre = 0

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

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

Time

O(n)

Space

O(n)

Each node is created once and located in O(1) via the index map. Extra space is the hash map plus the recursion stack, which reaches O(n) for a skewed tree.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Cave Survey Rebuild is our own problem on the technique behind Construct Binary Tree from Preorder and Inorder Traversal: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free