Start learning free

LESSON 417 OF 536 · BINARY TREES

Build a Binary Tree from Preorder and Inorder in JavaScript: O(n)

Practice O(n) Read the full explanation

Two arrays describe the same binary tree:

preorder lists the values in preorder: first a node, then its whole left subtree, then its whole right subtree.
inorder lists the values in inorder: first a node's whole left subtree, then the node, then its whole right subtree.

All the values are different. Build the tree and return its root.

The tests print the tree you return level by level, from left to right, with null where a child is missing and the trailing nulls left out. For example, [1,2,null,3] is the tree with root 1, 2 as its left child and 3 as the left child of 2.

Example 1:

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

Explanation: preorder starts with 3, so 3 is the root. In inorder, 9 is left of 3 and 15, 20, 7 are right of it: 9 is the left subtree and 15, 20, 7 are the right subtree. The right subtree's values come next in preorder, starting with 20, its root; in inorder 15 is left of 20 and 7 is right of it.

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
Explanation: A single value is a tree with only a root.

Example 3:

Input: preorder = [1,2,3], inorder = [3,2,1]
Output: [1,2,null,3]
      1
     /
    2
   /
  3

Explanation: In inorder, every value comes before its parent, so each node has only a left child. The same preorder with inorder = [1,2,3] would give a line going right: [1,null,2,null,3].

Constraints:

1 <= preorder.length <= 3000
inorder.length == preorder.length
Every value is between -3000 and 3000, and the values are all different.
preorder and inorder are the preorder and inorder traversals of the same tree.
The tree is at most 400 levels deep.

Note:

The solution should run in O(n) time, where n is the number of values: build each node once, and find where a value sits in inorder with a dictionary instead of a search.

STEP 1 OF 13

Guided

Ctrl + Enter to check

JAVASCRIPT · BINARY TREES

Construct Binary Tree From Preorder And Inorder Traversal in JavaScript, explained

Problem overview

buildTree(preorder, inorder) receives two arrays that list the same tree's values in two orders and returns the tree's root. Preorder lists a node, then its whole left subtree, then its whole right subtree. Inorder lists the left subtree, then the node, then the right subtree. All values are different. The lesson provides TreeNode, which is built as new TreeNode(val) and has val, left and right fields, the last two starting as null.

For preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7], the tests print the tree level by level as [3,9,20,null,null,15,7]: the root is 3, with 9 on the left and 20 on the right, and 20 has the children 15 and 7.

Approach: preorder names the roots, inorder splits the sides

Preorder always starts with the root. Inorder then shows where that root sits: everything to its left belongs to the left subtree and everything to its right belongs to the right subtree. In the example the root 3 is at index 1 of inorder, so [9] is the left subtree and [15,20,7] is the right one.

The same idea repeats on each side. The next value in preorder after the root is the root of the left subtree, and once the left subtree is used up, the value after it is the root of the right subtree. So one counter walking through preorder gives the roots in exactly the order the recursion needs them, and a pair of indexes lo and hi says which stretch of inorder the current subtree occupies.

The only repeated question is "where is this value in inorder?". Searching the array each time costs O(n) per node, which is O(n²) in total for a long chain. Because the values are all different, a Map from value to index, filled once, answers in O(1).

Step by step

Create the map as this.inorderIndex = new Map(). A property on this is visible to every method, so the helper can read it.
Loop over inorder with i from 0 while i < inorder.length.
Store each pair with this.inorderIndex.set(inorder[i], i).
Start the preorder counter with this.preIndex = 0: the position of the next root to use.
Return the helper's result for the whole of inorder: this.build(preorder, 0, inorder.length - 1).
Declare the helper build(preorder, lo, hi). lo and hi are the first and last index of the part of inorder holding this subtree.
Stop on an empty range: if lo > hi, return null. Below a leaf, both ranges are empty.
Take the next root: read preorder[this.preIndex] into value, then move the counter forward.
Create the node with new TreeNode(value).
Find the split: mid is this.inorderIndex.get(value).
Build the left subtree first from lo to mid - 1. Its roots come right after this node in preorder.
Then the right subtree from mid + 1 to hi. The left call has used all its roots, so the counter points at the right subtree's root.
Return the node.

The solution in JavaScript

class Solution {
    build(preorder, lo, hi) {
        if (lo > hi) {
            return null;
        }
        let value = preorder[this.preIndex];
        this.preIndex++;
        let node = new TreeNode(value);
        let mid = this.inorderIndex.get(value);
        node.left = this.build(preorder, lo, mid - 1);
        node.right = this.build(preorder, mid + 1, hi);
        return node;
    }

    buildTree(preorder, inorder) {
        this.inorderIndex = new Map();
        for (let i = 0; i < inorder.length; i++) {
            this.inorderIndex.set(inorder[i], i);
        }
        this.preIndex = 0;
        return this.build(preorder, 0, inorder.length - 1);
    }
}

Details worth knowing:

Order matters. The left subtree must be built before the right one, because the counter only works if it is consumed in preorder. Swapping the two build lines pairs the roots with the wrong ranges.
State on this. preIndex and inorderIndex are properties of the object, set at the start of buildTree. Each call to buildTree resets them, so one Solution object can be used for several inputs.
Map instead of an object. A Map works with number keys directly, and get returns undefined for a missing key. Here every value is present, because both arrays hold the same values.
The counter is shared. this.preIndex++ changes the property in place, and the next call, even one made in the recursion, sees the new value.

Complexity

Time: O(n). Filling the map takes n steps. Each call of build that doesn't return early creates exactly one node, so there are n of those and at most n + 1 calls that return null. Each call does a constant amount of work, because the map lookup is O(1).

Space: O(n). The map holds n entries, and the recursion goes as deep as the tree, which is at most n levels (400 in this lesson).

Edge cases and common mistakes

A single value. preorder = [-1] with inorder = [-1] gives [-1]: the root's two ranges are empty, so both children are null.
All left children. preorder = [1,2,3] with inorder = [3,2,1] gives [1,2,null,3], a chain going left.
All right children. The same preorder with inorder = [1,2,3] gives [1,null,2,null,3].
Building the right subtree first. This reads the wrong values from preorder.
Using mid instead of mid - 1 and mid + 1. The root's own position would be included in a subtree, so its value would be placed a second time.
Passing the counter by value. If preIndex were a local variable passed as an argument, the right call would not see how far the left call had read. Keeping it on this avoids that.

Testing

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] gives [3,9,20,null,null,15,7].
preorder = [-1], inorder = [-1] gives [-1].
preorder = [1,2,3], inorder = [3,2,1] gives [1,2,null,3].
preorder = [1,2,3], inorder = [1,2,3] gives [1,null,2,null,3].
preorder = [1,2,3], inorder = [2,1,3] gives [1,2,3].

Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free