Construct Binary Tree from Preorder and Inorder Traversal

The problem

You are given two lists of the same values, taken from one binary tree in two different orders:

• preorder lists each node, then its left subtree, then its right subtree.
• inorder lists the left subtree, then the node, then the right subtree.

Rebuild the tree and return its root. All values are different, which makes the tree unique.

Trees in the output are written level by level, from left to right. null marks a missing child.

Example 1

Input: preorder = [5, 8, 1, 6, 3, 2], inorder = [1, 8, 5, 3, 6, 2]

Output: [5, 8, 6, 1, null, 3, 2]

Preorder starts with 5, so 5 is the root. In inorder, 1 and 8 are left of 5 and 3, 6, 2 are right of it. The same split repeats inside each side.

Example 2

Input: preorder = [7], inorder = [7]

Output: [7]

One value makes a tree with one node.

Example 3

Input: preorder = [1, 2, 3], inorder = [3, 2, 1]

Output: [1, 2, null, 3]

In inorder, everything sits left of 1, and then left of 2. So the tree leans all the way left.

Constraints

• 1 ≤ n ≤ 3,000, where n is the length of both lists.
• -3,000 ≤ value ≤ 3,000
• All values are different, and both lists come from the same tree.

Clarifying questions

Can values repeat?

No. That matters: with repeats, one value could sit in two places in inorder, and the split would be unclear.

Are the two lists always consistent?

Yes. They always come from one real tree, so no error checks are needed.

Is the tree a BST?

No. It can be any binary tree. Only the two orders tell us the shape.

How deep can the tree be?

Up to n = 3,000 levels if it is a chain, so the recursion can get that deep.

Spot the pattern

Each traversal holds one half of the information. Preorder says which value is the root: it is always listed first. Inorder says where the root splits its part into left and right. Splitting a part and then solving each side the same way is a tree traversal run backwards: recursion that builds the tree instead of reading it.

Solutions

Brute forceO(n²)OptimalO(n)

Show all

This problem has two approaches. There is no useful step between them.

Brute force O(n²)

The idea

The first value in preorder is the root of the whole tree. Find it in inorder. Everything to its left in inorder belongs to the left subtree, and everything to its right belongs to the right subtree.

Then build the left subtree from its part of inorder, and the right subtree from its part. Preorder lists the whole left subtree before the right one, so a single pointer preorder_index that moves forward through preorder always gives the root of the part being built, as long as we build the left side first.

The slow step is finding the root in inorder. Here it is a plain search from the start of the part.

Walkthrough

preorder

508112633425

preorder_index

inorder

108152336425

1. preorder_index = 0
2. def build(start, end): # inorder[start..end]
3. if start > end: return None
4. node = TreeNode(preorder[preorder_index]); preorder_index += 1
5. root_index = start
6. while inorder[root_index] != node.val: root_index += 1
7. node.left = build(start, root_index - 1)
8. node.right = build(root_index + 1, end)
9. return node
10. return build(0, len(inorder) - 1)

Preorder lists a root before its subtrees. Inorder lists the left subtree, then the root, then the right subtree. The box marks the part of inorder being built.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private int[] preorder, inorder;
    private int preorderIndex = 0;

    // Brute force: the next preorder value is the root of the current part;
    // search inorder for it to split left from right. Up to n * n steps.
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return build(0, inorder.length - 1);
    }

    // Builds the tree whose values are inorder[start..end].
    private TreeNode build(int start, int end) {
        if (start > end) return null;
        // Preorder lists a root before its subtrees, so the next
        // unused preorder value is the root of this part.
        TreeNode node = new TreeNode(preorder[preorderIndex++]);
        // Find the root in inorder: left of it is the left subtree.
        int rootIndex = start;
        while (inorder[rootIndex] != node.val) rootIndex++;
        // Build the left side first, because preorder lists it first.
        node.left = build(start, rootIndex - 1);
        node.right = build(rootIndex + 1, end);
        return node;
    }
}

Big O

Time O(n²)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line is the search: each run checks one inorder value. It runs inside every call that makes a node, so it is the work that grows. Each check is a fixed job, so it counts as 1 step. The rest of a call is a fixed job too, and there is one call per node.

   1. preorder_index = 0
   2. def build(start, end): # inorder[start..end]
   3. if start > end: return None
   4. node = TreeNode(preorder[preorder_index]); preorder_index += 1
   5. root_index = start
   6. while inorder[root_index] != node.val: root_index += 1
   7. node.left = build(start, root_index - 1)
   8. node.right = build(root_index + 1, end)
   9. return node
   10. return build(0, len(inorder) - 1)

2. 2 Count the runs on Example 1

   The table shows each root, the part of inorder it was searched in, and how many checks it took to find it. Short parts are cheap. The first search is the longest, because the root sits in the middle.

   3 + 2 + 1 + 2 + 1 + 1 = 10 checks.

   root	5	8	1	6	3	2	total
   part of inorder	1 8 5 3 6 2	1 8	1	3 6 2	3	2
   checks to find it	3	2	1	2	1	1	10

3. 3 Write the count for any n

   The search starts at the left end of its part. So the worst case is a root that sits at the right end every time. That happens when the tree leans all the way left, like Example 3. Then the parts have sizes n, n − 1, … down to 1, and each search walks its whole part:

   n + (n − 1) + … + 1 = n × (n + 1) / 2 = ½n² + ½n

   Check it with Example 3: 3 × 4 / 2 = 6 checks, which is 3 + 2 + 1.

4. 4 Keep only the part that grows fastest

   • Drop the +½n. Next to ½n² it soon stops mattering.
   • Drop the ½. Halving every count does not change how fast it grows.

   What is left is n². The n calls themselves add only n more steps, which is a lower term.

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The new tree has n nodes, but it is the answer, so it does not count. The extra memory is the call stack: the calls that started and have not returned. At most h wait at once, where h is the height of the tree, and in a chain h = n. So the space is O(n).

   preorder_indexcall stack (h frames)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 3,000 nodes, that is 3,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Optimal O(n)

The idea

Keep everything from the brute force, and fix the slow step. Before building, walk inorder once and store each value’s position in a hash map: a table that finds the entry for a key in one step. The values are all different, so each one has exactly one position.

Now finding the root of a part is one lookup, position_of[value], instead of a search.

Why it is correct: preorder always gives the root of the part being built next, and the root’s position in inorder splits that part exactly into its left and right subtree. The map changes how fast we find that position, not which position we find.

Walkthrough

preorder

508112633425

preorder_index

inorder

108152336425

value	1	8	5	3	6	2
index	0	1	2	3	4	5

1. position_of = {value: i for i, value in enumerate(inorder)}
2. preorder_index = 0
3. def build(start, end): # inorder[start..end]
4. if start > end: return None
5. node = TreeNode(preorder[preorder_index]); preorder_index += 1
6. root_index = position_of[node.val]
7. node.left = build(start, root_index - 1)
8. node.right = build(root_index + 1, end)
9. return node
10. return build(0, len(inorder) - 1)

First store where each value sits in inorder: 1 at 0, 8 at 1, 5 at 2, 3 at 3, 6 at 4, 2 at 5. Later each lookup is one step.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private int[] preorder;
    private int preorderIndex = 0;
    private Map<Integer, Integer> positionOf = new HashMap<>();

    // Hash map: remember where each value sits in inorder, so splitting a
    // part takes one lookup instead of a search. One call per node, so n steps.
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        // Values are all different, so each one has exactly one position.
        for (int i = 0; i < inorder.length; i++) positionOf.put(inorder[i], i);
        return build(0, inorder.length - 1);
    }

    // Builds the tree whose values are inorder[start..end].
    private TreeNode build(int start, int end) {
        if (start > end) return null;
        // Preorder lists a root before its subtrees, so the next
        // unused preorder value is the root of this part.
        TreeNode node = new TreeNode(preorder[preorderIndex++]);
        // Left of the root in inorder is the left subtree.
        int rootIndex = positionOf.get(node.val);
        // Build the left side first, because preorder lists it first.
        node.left = build(start, rootIndex - 1);
        node.right = build(rootIndex + 1, end);
        return node;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are two parts. Filling the map does one step per value. Then each call of build does a fixed job: one check, one new node, one lookup and at most two more calls. So each map entry and each call counts as 1 step.

   1. position_of = {value: i for i, value in enumerate(inorder)}
   2. preorder_index = 0
   3. def build(start, end): # inorder[start..end]
   4. if start > end: return None
   5. node = TreeNode(preorder[preorder_index]); preorder_index += 1
   6. root_index = position_of[node.val]
   7. node.left = build(start, root_index - 1)
   8. node.right = build(root_index + 1, end)
   9. return node
   10. return build(0, len(inorder) - 1)

2. 2 Count the runs on Example 1

   Filling the map takes 6 steps, one per value. Then build is called once for each of the 6 values, and once for each empty part. Every node has two children spots, 12 in all, and 5 of them hold a node, so 7 are empty.

   6 + 6 + 7 = 19 steps.

   part	fill the map	calls with a node	calls on an empty part	total
   steps	6	6	7	19

3. 3 Write the count for any n

   The map takes n steps. A tree of n nodes has n + 1 empty child spots, and each node and each empty spot gets one call:

   n + n + (n + 1) = 3n + 1 steps

   Check it with Example 1: 3 × 6 + 1 = 19.

4. 4 Keep only the part that grows fastest

   • Drop the + 1. A fixed extra step does not change the growth.
   • Drop the 3. When n doubles, 3n doubles too.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The map holds n entries. The call stack holds up to h calls, and h is at most n. Both grow with n, so the space is O(n).

   position_of (n entries)preorder_indexcall stack (h frames)

Very deep trees

Each recursive call waits until the calls below it finish. If the tree is one long line of 3,000 nodes, that is 3,000 calls waiting at once. The algorithm is still right, but every language limits how many calls can wait, so a very deep tree can crash with a "stack overflow". Here is how to raise the limit:

• Python: stops at 1,000 calls. The code above raises it with sys.setrecursionlimit.
• Java: run with java -Xss64m, or run the work in new Thread(null, task, "main", 64L << 20).
• C#: run the work in new Thread(task, 64 * 1024 * 1024).
• TypeScript (Node): run with node --stack-size=30000.
• Go: nothing to do. Its stack grows by itself.

Recursion is still the answer interviewers expect for trees. Mention the limit out loud: "for a very deep tree, I would raise the stack limit or keep my own stack in a loop."

Common mistake

Building the right side first

The pointer preorder_index walks preorder from left to right, and preorder lists the whole left subtree before the right one. If the code builds the right subtree first, it takes left-subtree values as right-side roots, and the tree comes out wrong.

Tested at the limits

2,000 random trees of 1 to 10 nodes, in every shape. From their preorder and inorder lists, the brute force and the optimal solution both rebuilt the exact tree every time.

Largest inputs	Result
3,000 values (the most allowed), a balanced tree. Optimal.	0.001 s, and about 0.5 MB of extra memory: the new tree and the map of positions, which is the O(n) space.
3,000 values in one long line. Optimal.	0.002 s, and about 1 MB of extra memory: the same, plus 3,000 calls that wait at once.
3,000 values in one long line to the left. Brute force.	0.14 s. Each search for the root walks along the inorder list, about 4.5 million steps in total. The map makes each search one step.