Construct Binary Tree From Preorder And Inorder Traversal

The problem

Two lists, preorder and inorder, describe the same binary tree, in which all values are different. Build that tree and return its top node, the root. preorder holds the values in this order: a node, then its whole left subtree (its left child and everything below that child), then its whole right subtree. inorder puts a node's whole left subtree first, then the node, then its whole right subtree. Each rule applies again inside every subtree. Each node you build has a number val and two children, left and right; a missing child is null. For two empty lists return null.

What to write

type TreeNode = {val:number;left:TreeNode|null;right:TreeNode|null};

function solve(preorder: number[], inorder: number[]): TreeNode | null

Input
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Output
{"val":3,"left":{"val":9,"left":null,"right":null},"right":{"val":20,"left":{"val":15,"left":null,"right":null},"right":{"val":7,"left":null,"right":null}}}

Input
preorder = [-1]
inorder = [-1]

Output
{"val":-1,"left":null,"right":null}

Constraints

Return nested {val, left, right} nodes.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   All the values are different, so a value from preorder can be found at exactly one place in inorder. Without that promise, the same two lists could describe more than one tree.

2. Hint 2: Ask a smaller question

   Look at the first example. Which node of the tree does preorder name first? Now find that value in inorder. What can you say about the values on its left there, and the values on its right?

3. Hint 3: Name the pattern

   The first value of preorder is the root. In inorder, everything before the root is its left subtree and everything after it is its right subtree, and each side is the same task again on fewer values. Making a node first and then handing each child its part is preorder tree recursion. Read the lesson on preorder tree recursion.

4. Hint 4: State the invariant

   Every call receives one stretch of inorder, which holds exactly the values of one subtree. Unless the stretch is empty, the next unused value of preorder is the root of that subtree, because preorder names a root before everything below it and finishes the left subtree before starting the right.

5. Hint 5: Sketch the pseudocode

   Map each value to its position in inorder, and keep one shared position in preorder. build(low, high): if low is past high, return no node. Take the next preorder value as the root and let m be its position in inorder. Left child: build(low, m - 1). Then right child: build(m + 1, high). Start with the whole list.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Preorder chooses the next root; its inorder index divides the left and right subtree ranges.

The slow way

Take the first value of preorder as the root, search inorder for it, copy the values on each side into new lists and repeat on both sides. It is correct, but every node costs a search and some copying. In a tree that is one long chain of left children, the searches alone add up to about n × n / 2 steps.

The insight

preorder tells you which value is a root, and inorder tells you which values belong on each side of it. A subtree does not need its own copies of the lists: it is one stretch of inorder, marked by two positions, and its values come next in preorder. A map from value to position replaces every search.

Step by step

1. Record where each value sits in inorder. Every node has to be found in inorder. A map from value to position answers that in one step, where a search through the list would take up to n.
2. Read preorder from its first value, one value per node. preorder names a root before everything below it. One position that only moves forward, shared by all the calls, points at the root of the next subtree that is not empty.
3. Build the subtree that fills one stretch of inorder. The values of a subtree always sit next to each other in inorder. So two positions, the first and the last, describe a whole subtree and nothing has to be copied.
4. An empty stretch holds no node. When the first position has passed the last one, there are no values on that side of the parent, so that child is missing.
5. Take the next preorder value as the root and find it in inorder. Every earlier value of preorder was taken by a node above this subtree or to its left, so the next one is its root. Its place in inorder shows which values go on each side.
6. Build what lies left of it first, then what lies right of it. preorder lists the whole left subtree before the right one. So the left side must take its values first, and what follows then belongs to the right side.
7. The whole of inorder is the stretch for the full tree. The full tree is the subtree that holds every value, so its stretch runs from the first position of inorder to the last.

The same numbered steps are the comments in each solution.

function solve(preorder, inorder) {
  // 1. Record where each value sits in inorder
  const indexes = new Map(inorder.map((v, i) => [v, i]));
  // 2. Read preorder from its first value, one value per node
  let next = 0;
  // 3. Build the subtree that fills one stretch of inorder
  function build(l, r) {
    // 4. An empty stretch holds no node
    if (l > r) return null;
    // 5. Take the next preorder value as the root and find it in inorder
    const val = preorder[next++],
      mid = indexes.get(val);
    // 6. Build what lies left of it first, then what lies right of it
    return { val, left: build(l, mid - 1), right: build(mid + 1, r) };
  }
  // 7. The whole of inorder is the stretch for the full tree
  return build(0, inorder.length - 1);
}

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };
function solve(preorder: number[], inorder: number[]): TreeNode | null {
  // 1. Record where each value sits in inorder
  const indexes = new Map(inorder.map((v, i) => [v, i]));
  // 2. Read preorder from its first value, one value per node
  let next = 0;
  // 3. Build the subtree that fills one stretch of inorder
  function build(l: number, r: number): TreeNode | null {
    // 4. An empty stretch holds no node
    if (l > r) return null;
    // 5. Take the next preorder value as the root and find it in inorder
    const val = preorder[next++],
      mid = indexes.get(val)!;
    // 6. Build what lies left of it first, then what lies right of it
    return { val, left: build(l, mid - 1), right: build(mid + 1, r) };
  }
  // 7. The whole of inorder is the stretch for the full tree
  return build(0, inorder.length - 1);
}

def solve(preorder, inorder):
    # 1. Record where each value sits in inorder
    indexes = {val: i for i, val in enumerate(inorder)}
    # 2. Read preorder from its first value, one value per node
    roots = iter(preorder)

    # 3. Build the subtree that fills one stretch of inorder
    def build(low, high):
        # 4. An empty stretch holds no node
        if low > high:
            return None
        # 5. Take the next preorder value as the root and find it in inorder
        val = next(roots)
        mid = indexes[val]
        # 6. Build what lies left of it first, then what lies right of it
        return TreeNode(val, build(low, mid - 1), build(mid + 1, high))

    # 7. The whole of inorder is the stretch for the full tree
    return build(0, len(inorder) - 1)

Example 1, traced

Input
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Output
{"val":3,"left":{"val":9,"left":null,"right":null},"right":{"val":20,"left":{"val":15,"left":null,"right":null},"right":{"val":7,"left":null,"right":null}}}

Why it works

preorder lists a root, then its whole left subtree, then its whole right subtree. So right after a root come the values of its left subtree, exactly as many as inorder shows on its left. Building the left side first uses up those values and leaves the root of the right subtree next in line.

Time and space

Time O(n), extra space O(n). Each value goes into the map once and is taken from preorder once, and each node costs one lookup, so the time is O(n). The map holds n entries, and in a tree shaped like a chain the calls nest n deep, so the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Build the left part before the right part. The other way round, the right part of the first example takes 9 as its root, a value that belongs on the left, and the program fails.
• All calls must share one position in preorder. If each call hands its own position to both children, the right child cannot know how many values the left side used, and it starts from the wrong root.
• Do not search inorder for the root in every call. The tree comes out right, but for a chain of 1,000 left children the searches look at 500,500 values in total, where the map needs 1,000 lookups.

Pattern

Preorder tree recursion. Builds on Validate Binary Search Tree and Kth Smallest Element In a Bst.

Keep going