Start learning free

LESSON 416 OF 535 · BINARY TREES

Construct Binary Tree from Preorder and Inorder in C++: O(n) with a Map

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 an unordered_map instead of a search.

STEP 1 OF 13

Guided

Ctrl + Enter to check

C++ · BINARY TREES

Construct Binary Tree From Preorder And Inorder Traversal in C++, explained

Problem overview

The method buildTree receives two vectors, preorder and inorder, which are the preorder and inorder traversals of the same binary tree. All values are different. It must build the tree and return its root as a TreeNode*. The lesson provides TreeNode: a struct with an int val, pointers left and right, and a constructor TreeNode(int x) that sets both pointers to NULL.

In preorder, a node comes first, then its whole left subtree, then its whole right subtree. In inorder, the left subtree comes first, then the node, then the right subtree. The tests print the tree level by level, with null for a missing child.

For preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7] the result is [3,9,20,null,null,15,7]: 3 is the root, 9 is its left child, and 20 is its right child with children 15 and 7.

Approach: preorder names the root, inorder splits the rest

Two facts about the traversals solve the problem:

The first value of preorder is the root.
In inorder, everything to the left of the root's position belongs to the left subtree, and everything to the right belongs to the right subtree.

In the example, 3 comes first in preorder. In inorder, 9 sits left of 3, so the left subtree is just 9, and 15, 20, 7 sit right of 3, so they make the right subtree. The same idea then applies to each part. Preorder lists a subtree's values as one block, so the next unused value in preorder is always the root of the next subtree to build: after the root come all the roots of the left subtree, then those of the right subtree.

The only repeated work is finding where a value sits in inorder. Scanning for it each time costs O(n) per node and O(n²) in total for a chain-shaped tree. Because the values are all different, each one has exactly one position, so an unordered_map from value to index answers in O(1) after one pass to fill it. That brings the whole solution to O(n).

Step by step

Keep a value-to-index map. Declare unordered_map<int, int> inorderIndex as a member of the class, so the helper written later can read it as well.
Keep a position in preorder. The member int preIndex = 0 marks the next root to use. Reading preorder from left to right gives the roots in the order the recursion builds them.
Loop over inorder in buildTree, with i from 0 while i < inorder.size().
Fill the map. Inside the loop, inorderIndex[inorder[i]] = i.
Start the recursion. Return build(preorder, 0, inorder.size() - 1): the whole of inorder is the whole tree.
Declare the helper. build takes preorder and two ints, lo and hi, the first and last index of the part of inorder that holds this subtree. It returns the subtree's root.
Stop on an empty range. If lo > hi, return NULL. Below a leaf, both ranges are empty.
Take the next root. Read preorder[preIndex] into value, then add 1 to preIndex.
Create the node with new TreeNode(value) and keep the pointer in node.
Find the split. mid is inorderIndex[value]. Positions lo to mid - 1 are the left subtree and mid + 1 to hi the right one.
Build the left subtree first. node->left = build(preorder, lo, mid - 1). Its roots come right after this node in preorder.
Then the right subtree, from mid + 1 to hi. By now the left subtree has used all of its roots, so preIndex points at the right subtree's root.
Return node.

The solution in C++

class Solution {
public:
    unordered_map<int, int> inorderIndex;
    int preIndex = 0;

    TreeNode* build(vector<int>& preorder, int lo, int hi) {
        if (lo > hi) {
            return NULL;
        }
        int value = preorder[preIndex];
        preIndex++;
        TreeNode* node = new TreeNode(value);
        int mid = inorderIndex[value];
        node->left = build(preorder, lo, mid - 1);
        node->right = build(preorder, mid + 1, hi);
        return node;
    }

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

Here is what the recursion does on the first example. Each line shows the value taken from preorder, the range it was called with, and the position of that value in inorder:

value=3 lo=0 hi=4 mid=1
value=9 lo=0 hi=0 mid=0
value=20 lo=2 hi=4 mid=3
value=15 lo=2 hi=2 mid=2
value=7 lo=4 hi=4 mid=4

The values come out in exactly the order of preorder. The root 3 splits the range 0 to 4 at position 1. The left call gets 0 to 0, which holds only 9. The right call gets 2 to 4 and takes the next preorder value, 20, which splits it at position 3, leaving 15 on the left and 7 on the right. Each of those calls gets a one-element range, and each of their own children calls gets an empty range and returns NULL.

The C++ details worth a closer look:

Members as shared state. inorderIndex and preIndex belong to the object, so every recursive call sees and updates the same values. That is what lets preIndex advance across calls without being passed around. It also means one Solution object is built for one tree: calling buildTree a second time on the same object starts with preIndex already at the end of the vector, and reading preorder[preIndex] past the end is undefined behaviour. Use a fresh object, or reset preIndex to 0 first.
Passing by reference. vector<int>& preorder avoids copying the vector at every recursive call.
operator[] on a map. inorderIndex[value] inserts a default entry if the key is missing. Here every value is in the map because the two traversals come from the same tree, so it only reads.
Signed and unsigned. inorder.size() is unsigned. In build(preorder, 0, inorder.size() - 1) the result converts to int, which is fine for non-empty input, and the constraints guarantee at least one value. For an empty vector the subtraction would wrap around.
Memory. Each new TreeNode gives the caller a node to own. The lesson does not free them, which is normal for this kind of exercise.

Complexity

Time: O(n). The loop that fills the map runs n times with O(1) work per insertion on average. build then creates exactly one node per value, and each call besides those does only constant work: there are n calls that create a node and n + 1 that return NULL.

Space: O(n). The map holds n entries, and the tree itself has n nodes. The recursion goes as deep as the tree is tall, up to n levels for a chain, and at most 400 for the lesson's inputs.

Edge cases and common mistakes

A single value. preorder = [-1], inorder = [-1] gives [-1]: one node whose two ranges are empty.
Only left children. preorder = [1,2,3] with inorder = [3,2,1] gives [1,2,null,3], since every value comes before its parent in inorder. With inorder = [1,2,3] instead, the same preorder gives [1,null,2,null,3], a chain going right.
Building the right subtree first. Preorder lists the left subtree before the right one, so the left call must come first. Swapping the two calls would hand the left subtree's roots to the right subtree.
Wrong ranges. The two recursive calls use mid - 1 and mid + 1. Using mid in either range would include the node itself again, so the tree comes out wrong and preIndex can run past the end of preorder.
Passing preIndex by value. Each call would then get its own copy, and the right subtree would start from the wrong root. A member variable, as here, avoids that.
Searching instead of using the map. Finding the root's position with a loop works but takes O(n) per node, O(n²) overall for a degenerate tree.

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].
preorder = [1,2,4,5,3], inorder = [4,2,5,1,3] gives [1,2,3,4,5].

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

Start learning free