Construct Binary Tree from Preorder and Inorder Traversal

Medium
1907.

Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal is a medium coding problem on arrays, hash table and trees, asked in Amazon, Google, Microsoft and Bloomberg interviews.

You are given two integer arrays: preorder, the preorder traversal of a binary tree (node, left subtree, right subtree), and inorder, the inorder traversal of the same tree (left subtree, node, right subtree). All values are distinct.

Rebuild the 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]
Explanation
3 comes first in preorder, so it is the root; in the inorder list 9 is to its left and 15, 20, 7 to its right. Repeating the split on each side gives the tree.

Example 2

Input
preorder = [-1], inorder = [-1]
Output
[-1]
Explanation
A single node.

Example 3

Input
preorder = [1,2,3], inorder = [3,2,1]
Output
[1,2,null,3]
Explanation
Every value sits left of its parent in the inorder list, so the tree is a chain of left children.

Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • all values are distinct
  • every value of inorder appears in preorder
  • the two arrays describe the same tree
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Construct Binary Tree from Preorder and Inorder Traversal Solution

Construct Binary Tree from Preorder and Inorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Construct Binary Tree from Preorder and Inorder Traversal is a medium coding problem on arrays, hash table and trees, asked in Amazon, Google, Microsoft and Bloomberg interviews.

Problem statement

You are given two integer arrays: preorder, the preorder traversal of a binary tree (node, left subtree, right subtree), and inorder, the inorder traversal of the same tree (left subtree, node, right subtree). All values are distinct.

Rebuild the 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]
Explanation: 3 comes first in preorder, so it is the root; in the inorder list 9 is to its left and 15, 20, 7 to its right. Repeating the split on each side gives the tree.

Example 2

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Explanation: A single node.

Example 3

Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,null,3]
Explanation: Every value sits left of its parent in the inorder list, so the tree is a chain of left children.

Constraints

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • all values are distinct
  • every value of inorder appears in preorder
  • the two arrays describe the same tree

Hints for Construct Binary Tree from Preorder and Inorder Traversal

  1. Hint 1

    The first value of a preorder traversal is always the root.

  2. Hint 2

    Find the root in the inorder list: everything to its left is the left subtree, everything to its right the right subtree — and the counts tell you how to split the preorder list too.

  3. Hint 3

    Recurse on index ranges rather than copying subarrays, keep a running pointer into preorder (it consumes roots in exactly the order the recursion needs them, left subtree first), and look positions up in a hash map instead of searching.

How to solve Construct Binary Tree from Preorder and Inorder Traversal

Preorder names each subtree's root first; inorder says which values lie left and right of it. Consuming preorder from the front while splitting inorder ranges rebuilds the tree top-down.

Approach

  1. Map every value to its index in inorder.
  2. Keep a pointer pos into preorder, starting at 0.
  3. To build the subtree whose values occupy inorder[lo..hi]: if lo > hi return null; otherwise take preorder[pos] as the root and advance pos.
  4. Let mid be the root's index in inorder; build the left subtree from [lo, mid - 1], then the right subtree from [mid + 1, hi].
  5. Return the root built for the whole range.

Why it works

Preorder lists a node, then its entire left subtree, then its entire right subtree. Building the left subtree completely before the right one therefore makes pos meet exactly the roots in the order they are needed. The inorder split is correct because, values being distinct, the root's position separates the left subtree's values from the right's.

Complexity

  • Time — O(n)
  • Space — O(n) for the map, O(h) for the recursion

Pitfalls

  • Building the right subtree before the left breaks the shared preorder pointer.
  • Searching for the root in inorder each time makes it O(n^2) on a chain.

Reference solution

Python

from typing import List, Optional

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

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

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

Java

public static 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);
    int[] pos = {0};
    return build(preorder, index, pos, 0, inorder.length - 1);
}

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

C++

TreeNode* buildRange(vector<int>& preorder, unordered_map<int, int>& index, int& pos, int lo, int hi);

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;
    int pos = 0;
    return buildRange(preorder, index, pos, 0, (int) inorder.size() - 1);
}

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

JavaScript

var buildTree = function(preorder, inorder) {
    var index = new Map(), pos = 0;
    for (var i = 0; i < inorder.length; i++) index.set(inorder[i], i);
    function build(lo, hi) {
        if (lo > hi) return null;
        var v = preorder[pos++];
        var node = new TreeNode(v);
        var mid = index.get(v);
        node.left = build(lo, mid - 1);
        node.right = build(mid + 1, hi);
        return node;
    }
    return build(0, inorder.length - 1);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets