Construct Binary tree from Inorder and preorder traversal

The problem, simply

You get two lists of the same tree's values. All values are different.

• preorder lists a node first, then everything in its left subtree, then everything in its right subtree.
• inorder lists everything in the left subtree, then the node, then everything in the right subtree. It is the tree read from left to right.

Build the tree and give back its root.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use the roll call idea directly. Walk through preorder one card at a time. Each card is the root of the window it lands in. Find it in inorder by looking at every card in the window.

1. Keep a finger p on preorder. Start with the whole inorder list as the window.
2. The card at p is the root of the window. Move p forward.
3. Search the window in inorder for that card. Call its position k.
4. Build the left child from the window left of k, then the right child from the window right of k. The left side must be built first, because preorder lists it first.

class Solution {
    private int p;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        p = 0;
        return build(preorder, inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] pre, int[] in, int lo, int hi) {
        if (lo > hi) return null;                   // empty window, no node
        TreeNode root = new TreeNode(pre[p++]);
        int k = lo;
        while (in[k] != root.val) k++;              // search the window
        root.left = build(pre, in, lo, k - 1);
        root.right = build(pre, in, k + 1, hi);
        return root;
    }
}

How long it takes: each node may search a window as long as the whole list. For a stick shaped tree that adds up to O(n^2). Extra room: the waiting helpers, up to O(n) deep.

Way 2: the clever way

The search is the slow part. Before we start, write down where every value sits in inorder, in a map. Then finding k is one quick lookup.

1. Fill a map from value to its index in inorder.
2. Build exactly as before, but get k from the map.

import java.util.*;

class Solution {
    private int p;
    private Map<Integer, Integer> where = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        p = 0;
        where.clear();
        for (int i = 0; i < inorder.length; i++) where.put(inorder[i], i);
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] pre, int lo, int hi) {
        if (lo > hi) return null;
        TreeNode root = new TreeNode(pre[p++]);    // next roll call name is the root
        int k = where.get(root.val);               // where it stands in the photo
        root.left = build(pre, lo, k - 1);         // left group first
        root.right = build(pre, k + 1, hi);
        return root;
    }
}

How long it takes: one quick lookup per node, O(n). Extra room: the map plus the waiting helpers, O(n).

Watch out for

• Repeated values break the idea. If two nodes hold the same value, you cannot tell which one the map means, and many trees can fit the lists.
• Forgetting to reset p and the map between calls when they are fields.
• Copying sub arrays with Arrays.copyOfRange at every step. It works, but it costs O(n^2) time and room. Pass window bounds instead.

What interviewers ask next

• Inorder and postorder instead? Postorder ends with the root. Walk it from the back, and build the right side before the left side. That is LeetCode 106.
• Preorder and postorder? Not enough in general. A node with one child could have it on the left or on the right, and both lists look the same. If every node has 0 or 2 children, it works (LeetCode 889).
• A binary search tree from preorder alone? Yes. Inorder of a search tree is just the sorted values, or use bounds and build in O(n) (LeetCode 1008).
• Can you do it without the map and without recursion? Yes, with a stack and two fingers, one on each list. It is a nice O(n) trick but harder to explain on a whiteboard.

Remember this

Grown-up words: the roll call is the preorder traversal, the class photo is the inorder traversal, the groups are subtrees, the photo window is an index range, and splitting the job into two smaller jobs is divide and conquer.