Construct Binary Tree from Preorder and Inorder Traversal

Q: Why do you need both preorder and inorder to rebuild a binary tree?

Preorder alone does not fix the shape. The preorder [1, 2] fits a tree where 2 is the left child of 1 and one where it is the right child. Inorder settles it: [2, 1] puts 2 on the left, [1, 2] on the right. With distinct values, the pair describes exactly one tree.

Q: What is the time complexity of building a binary tree from preorder and inorder?

With a map from value to inorder position, it is O(n) time and O(n) extra space. Without the map, scanning each inorder range for its root costs O(n·h) , which becomes O(n²) on a tree shaped like a path.

Q: Can you rebuild a binary tree from preorder and postorder?

Not in general. Preorder [1, 2] and postorder [2, 1] fit both a left child and a right child, because neither traversal puts the root between its subtrees. The pair is enough only for a full binary tree, where every node has zero or two children.

MediumTree traversal Hashing Recursion

+10

You get two arrays, preorder and inorder, that list the distinct values of the same binary tree. Preorder visits a node, then its left subtree, then its right subtree. Inorder visits the left subtree, then the node, then the right subtree.

Rebuild the tree and return it as an array in level order: the root at index 0, the children of index i at 2i+1 (left) and 2i+2 (right), and -1 for every empty spot. The array ends at the last node, with no trailing -1.

Function

buildTree(preorder: integer-array, inorder: integer-array) → integer-array

preorderinteger-array: the values in preorder: node, left subtree, right subtree
inorderinteger-array: the values in inorder: left subtree, node, right subtree
Returnsinteger-array: the tree in level order, with -1 for empty spots and no trailing -1

Constraints

1 ≤ preorder.length ≤ 3000
inorder.length == preorder.length
0 ≤ preorder[i] ≤ 10⁴, and all values are distinct.
inorder holds the same values, and both arrays describe the same binary tree.
The depth of the tree is at most 14, so every index in the answer is below 2¹⁴-1 = 16383.

Examples

Input: preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
Output: [7, 3, 4, 0, 9, -1, 6]
Explanation: Preorder starts with the root, 7. It sits at inorder position 3, so 0, 3, 9 go left and 4, 6 go right. 4 has only a right child, 6, so index 5 stays -1.

Input: preorder = [1, 2, 3]inorder = [2, 3, 1]
Output: [1, 2, -1, -1, 3]
Explanation: The root 1 comes last in inorder, so index 2 is -1. Of 2, 3, preorder lists 2 first and inorder puts 3 after it, so 3 is its right child, at index 4.

Follow-up

Can you rebuild the tree without recursion, in one pass over preorder with an explicit stack?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Preorder gives the root of every subtree: the first value of its stretch. Inorder gives the split: values before the root go left, values after it go right. Recursing on both halves rebuilds the tree, and a map from value to inorder position makes each root lookup one step.

Split recursively, scanning for the root

Intuition

In preorder, the left subtree follows its root and takes one entry per value, m-lo of them, where m is the root's inorder position. The right subtree comes after it, so its root sits at pre+1+(m-lo). In the first example the left part 0, 3, 9 has three values, so the right subtree starts at preorder index 4, the value 4.

A depth of at most 14 keeps every output index below 2^14-1. Fill that many cells with -1, write each value at its index, and cut the trailing -1 entries at the end.

Scanning each inorder range for its root costs O(n·h): ranges on one level do not overlap, so a level scans at most n entries, at most 14 × 3000 = 42000 steps here. With no depth limit, a tree shaped like a path makes it O(n²).

Algorithm

Create out with 2^14-1 entries, all -1.
Write build(pre, lo, hi, h): if lo > hi, return. Otherwise write preorder[pre] to out[h].
Scan inorder from lo to find the root's position m. The left subtree has m-lo values.
Call build(pre+1, lo, m-1, 2*h+1) and build(pre+1+(m-lo), m+1, hi, 2*h+2).
Call build(0, 0, n-1, 0), then drop the trailing -1 entries and return the rest.

def buildTree(preorder, inorder):
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = lo
        while inorder[m] != value:  # find the root in the inorder range
            m += 1
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Split recursively with a position map

Intuition

The values are distinct, so each has exactly one position in inorder. Record it in a map from value to position before the recursion starts, and every root lookup becomes one step.

Building the map takes O(n), and each value is then placed once with constant work, so the total is O(n) time. The map takes O(n) space and the recursion one frame per level. In C and R the values are at most 10^4, so a plain array of 10^4+1 entries serves as the map.

Algorithm

Build a map from each value of inorder to its position.
Create out with 2^14-1 entries, all -1.
In build(pre, lo, hi, h), return if lo > hi; otherwise write preorder[pre] to out[h] and look up its position m in the map.
Recurse with build(pre+1, lo, m-1, 2*h+1) and build(pre+1+(m-lo), m+1, hi, 2*h+2).
Call build(0, 0, n-1, 0), then drop the trailing -1 entries and return the rest.

def buildTree(preorder, inorder):
    position = {value: i for i, value in enumerate(inorder)}  # value -> inorder index
    out = [-1] * (2 ** 14 - 1)  # every index of a depth-14 tree is below 2^14-1

    def build(pre, lo, hi, h):
        # preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
        # it goes to index h of the output.
        if lo > hi:
            return
        value = preorder[pre]
        out[h] = value
        m = position[value]
        left_size = m - lo
        build(pre + 1, lo, m - 1, 2 * h + 1)
        build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)

    build(0, 0, len(inorder) - 1, 0)
    last = len(out) - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Pitfalls and edge cases

Starting the right subtree at pre+1+m instead of pre+1+(m-lo). It works while lo is 0, as at the top call, and breaks once a range starts later.
Dropping the gaps. A missing child still holds its slot, so the second example answers [1, 2, -1, -1, 3], not [1, 2, 3].
Leaving trailing -1 entries. Returning all 2^14-1 cells gives the first example 16376 extra -1 entries.
Copying slices of both arrays at every call, which adds O(n) per level. Pass index ranges.
In Lua and R, arrays start at 1. Keep positions 0-based for the arithmetic and read preorder[pre + 1] and out[h + 1].

Frequently asked questions3

Why do you need both preorder and inorder to rebuild a binary tree?

Preorder alone does not fix the shape. The preorder [1, 2] fits a tree where 2 is the left child of 1 and one where it is the right child. Inorder settles it: [2, 1] puts 2 on the left, [1, 2] on the right. With distinct values, the pair describes exactly one tree.

What is the time complexity of building a binary tree from preorder and inorder?

With a map from value to inorder position, it is O(n) time and O(n) extra space. Without the map, scanning each inorder range for its root costs O(n·h), which becomes O(n²) on a tree shaped like a path.

Can you rebuild a binary tree from preorder and postorder?

Not in general. Preorder [1, 2] and postorder [2, 1] fit both a left child and a right child, because neither traversal puts the root between its subtrees. The pair is enough only for a full binary tree, where every node has zero or two children.

def buildTree(preorder, inorder):
    # Write code here

Test #1

Test #2

Arguments

preorder = [7, 3, 0, 9, 4, 6]
inorder = [0, 3, 9, 7, 4, 6]

Expected Output

[7, 3, 4, 0, 9, -1, 6]