Construct Binary Tree from Preorder and Inorder Traversal

mediumTrees: BST & Advanced73 stepsJava · Python · C++

The first preorder value is the root. Finding it in the inorder array splits inorder into left and right subtrees, and the left part's size tells you how much of preorder belongs to the left subtree. Recurse on both parts; a map from value to inorder index keeps it O(n).

▶ Watch the animated trace

Traced input: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7] → [3,9,20,null,null,15,7]. Original problem: neetcode.io/problems/binary-tree-from-preorder-and-inorder-traversal

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

Each node is created once; the index map is O(n).

Key idea

Preorder = root, left subtree, right subtree.
Inorder = left subtree, root, right subtree.
The root's inorder index splits the tree; mid - inLo is the left subtree size.
Consume preorder left to right with a single global index.

Common mistakes

Searching inorder linearly every call is O(n²).
Building the right subtree before the left when using a running preorder index.
Values must be unique for the map to work.

Solution

Java

int pre;

TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> index = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) index.put(inorder[i], i);
    pre = 0;
    return build(preorder, inorder, index, 0, inorder.length - 1);
}

TreeNode build(int[] preorder, int[] inorder, Map<Integer, Integer> index, int lo, int hi) {
    if (lo > hi) return null;
    int val = preorder[pre++];
    TreeNode node = new TreeNode(val);
    int mid = index.get(val);
    node.left = build(preorder, inorder, index, lo, mid - 1);
    node.right = build(preorder, inorder, index, mid + 1, hi);
    return node;
}

Python

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

    def build(lo: int, hi: int) -> Optional[TreeNode]:
        nonlocal pre
        if lo > hi: return None
        val = preorder[pre]
        pre += 1
        node = TreeNode(val)
        mid = index[val]
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node

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

C++

int pre;

TreeNode* build(vector<int>& preorder, unordered_map<int, int>& index, int lo, int hi) {
    if (lo > hi) return nullptr;
    int val = preorder[pre++];
    TreeNode* node = new TreeNode(val);
    int mid = index[val];
    node->left = build(preorder, index, lo, mid - 1);
    node->right = build(preorder, index, mid + 1, hi);
    return node;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> index;
    for (int i = 0; i < (int)inorder.size(); i++) index[inorder[i]] = i;
    pre = 0;
    return build(preorder, index, 0, (int)inorder.size() - 1);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single node Just the root.	`preorder = [-1], inorder = [-1]`	`[-1]`
Left-skewed Every root is the last inorder element of its range.	`preorder = [3, 2, 1], inorder = [1, 2, 3]`	`[3,2,null,1]`
Right-skewed Every left range is empty.	`preorder = [1, 2, 3], inorder = [1, 2, 3]`	`[1,null,2,null,3]`