Start learning free

LESSON 421 OF 540 · BINARY TREES

Construct Binary Tree from Preorder and Inorder in TypeScript: 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
    Ctrl + Enter to check

    TYPESCRIPT · BINARY TREES

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

    Problem overview

    buildTree receives two arrays that describe the same binary tree, preorder and inorder, and must return the root of that tree. All values are different. Preorder lists a node first, then its whole left subtree, then its whole right subtree. Inorder lists the left subtree, then the node, then the right subtree.

    The lesson provides the TreeNode class: it has val, left and right fields, and its constructor takes just the value and starts both children as null. The tests print the returned tree level by level, with null for missing children and the trailing nulls dropped.

    For preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7], the solution returns the tree printed as [3,9,20,null,null,15,7]: root 3, left child 9, right child 20, and 20 has children 15 and 7.

    Approach: preorder names the roots, inorder splits the sides

    Two facts do all the work.

    • The first value of preorder is the root. After it come the left subtree's roots, and only then the right subtree's.
    • In inorder, the root sits between its two subtrees. Everything to its left is the left subtree and everything to its right is the right subtree.

    So the first preorder value gives the root, and its position in inorder tells us which values go left and which go right. Each subtree is the same problem on a smaller stretch of inorder, and its root is the next unused value in preorder.

    The slow way is to search for the root inside the current stretch of inorder each time, which costs O(n) per node and O(n²) in total for a long, thin tree. Because the values are all different, we can instead record every value's position in inorder once, in a Map, and look it up in constant time.

    Step by step

    1. The map. A property inorderIndex, a Map<number, number>, will hold each value's index in inorder.
    2. The preorder counter. A property preIndex, starting at 0, is the position in preorder of the next root to use. Preorder lists roots in exactly the order we build them, so one counter that only moves forward is enough.
    3. Fill the map. In buildTree, loop over inorder and call this.inorderIndex.set(inorder[i], i) for each index. This costs O(n).
    4. Start the recursion. Return this.build(preorder, 0, inorder.length - 1). The pair lo and hi names the stretch of inorder that holds the current subtree's values, and the whole array is the whole tree.
    5. Empty range. In build, lo > hi means no values, so return null. This is where the recursion stops below every leaf.
    6. Take the root. Read preorder[this.preIndex] into value, then increase this.preIndex.
    7. Make the node with new TreeNode(value).
    8. Find the split. this.inorderIndex.get(value) gives mid, the root's position in inorder. Indices lo to mid - 1 are the left subtree and mid + 1 to hi the right one.
    9. Build the left subtree first, from lo to mid - 1. The order matters: in preorder, the left subtree's roots follow this node directly.
    10. Then the right subtree, from mid + 1 to hi. By then the left recursion has used all its roots, so preIndex points at the right subtree's root.
    11. Return the node.

    The solution in TypeScript

    class Solution {
    inorderIndex: Map<number, number> = new Map();
    preIndex: number = 0;

    build(preorder: number[], lo: number, hi: number): TreeNode | null {
        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: number[], inorder: number[]): TreeNode | null {
        for (let i = 0; i < inorder.length; i++) {
            this.inorderIndex.set(inorder[i], i);
        }
        return this.build(preorder, 0, inorder.length - 1);
    }
}

    TypeScript details

    • inorderIndex and preIndex are properties with initial values, so every method sees them through this. They live as long as the Solution object does.
    • Map.prototype.get returns number | undefined. The lesson compiles with --strict false, so mid - 1 is accepted. Under strict mode the compiler would complain that mid may be undefined. Here the lookup never fails, because every value in preorder also appears in inorder.
    • The types are erased when the code compiles to JavaScript. Nothing checks at run time that the two arrays really come from the same tree.
    • Arrays printed in the tests are plain numbers, so -1 and other negatives need no special treatment.

    Tracing the example

    Calling build on preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7] and printing each call that creates a node gives:

    lohipreIndex on entryroot taken
    0403
    0019
    24220
    22315
    4447

    The calls between them, such as lo = 0, hi = -1, have an empty range and return null without moving preIndex. Notice that the roots are taken in the order 3, 9, 20, 15, 7, which is exactly preorder.

    Complexity

    Time: O(n). Filling the map takes one pass. build creates each node once and does constant work per call besides the two recursive calls, and there are about 2n + 1 calls, counting the ones that return null.

    Space: O(n) for the map, plus the recursion stack, which is as deep as the tree (at most 400 levels here) and the nodes that are returned.

    Edge cases and common mistakes

    • Building the right side first. The counter moves through preorder in order, so the left subtree has to be built before the right one. Swapping the two lines attaches wrong values.
    • Passing the wrong ranges. The root at mid is excluded from both sides: mid - 1 and mid + 1, not mid.
    • Searching for the root every time. It works, but costs O(n²) on a long chain. The map avoids that.
    • Reusing a Solution object. The map and the counter are stored in the object. A second call to buildTree on the same object starts with preIndex left where the first call ended. With [1,2] and [2,1], the first call returns the tree [1,2] and the second one fails with "Maximum call stack size exceeded". Create a new Solution for each tree.
    • One-node trees. [-1] and [-1] give a node with two null children, printed as [-1].

    Testing

    Each pair below was run on a fresh Solution and the tree printed in level order:

    preorderinorderResult
    [3,9,20,15,7][9,3,15,20,7][3,9,20,null,null,15,7]
    [-1][-1][-1]
    [1,2,3][3,2,1][1,2,null,3]
    [1,2,3][1,2,3][1,null,2,null,3]
    [1,2,3][2,1,3][1,2,3]
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free