Construct Binary Tree From Preorder and Inorder Traversal

NeetCode: Construct Binary Tree From Preorder and Inorder Traversal · LeetCode: 105. Construct Binary Tree From Preorder and Inorder Traversal · Difficulty: Medium

Given the preorder and inorder traversals of a tree with unique values, rebuild the tree.

Example

Text

Input:  preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output: tree [3, 9, 20, null, null, 15, 7]

The first preorder value is always the root. In the inorder array, everything left of the root belongs to its left subtree and everything right of it to the right subtree.

The programs print the rebuilt tree in preorder, with N for a missing child, so the example prints 3,9,N,N,20,15,N,N,7,N,N. TreeNode has the fields val, left, and right; a missing child is null, so no wrapper type is needed.

Brute force: find the root by scanning

Take the root from the front of preorder, locate it in inorder with a linear search, and recurse on the two parts on either side. Arrays.copyOfRange(array, from, to) returns a new array holding the elements from index from up to but not including to.

Java

import java.util.Arrays;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        int root = preorder[0];
        int mid = 0;
        while (inorder[mid] != root) {
            mid++; // linear search for the root in inorder
        }
        TreeNode node = new TreeNode(root);
        node.left = buildTree(
            Arrays.copyOfRange(preorder, 1, mid + 1),
            Arrays.copyOfRange(inorder, 0, mid));
        node.right = buildTree(
            Arrays.copyOfRange(preorder, mid + 1, preorder.length),
            Arrays.copyOfRange(inorder, mid + 1, inorder.length));
        return node;
    }
}

public class Main {
    static String serialize(TreeNode root) {
        if (root == null) {
            return "N";
        }
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        TreeNode tree = s.buildTree(new int[] {3, 9, 20, 15, 7}, new int[] {9, 3, 15, 20, 7});
        System.out.println(serialize(tree));
        System.out.println(serialize(s.buildTree(new int[] {}, new int[] {})));
    }
}

Output

3,9,N,N,20,15,N,N,7,N,N
N

Each call copies its parts of both arrays, which costs O(n), and also scans for the root. Time: O(n²) worst case. Space: O(n²) worst case, because on a chain the copies from every active call are alive at once. The tree itself takes O(n).

Optimal: HashMap of inorder positions

The scan in the brute force only asks "where is this value in inorder?". Build a value -> index map once and that answer is O(1). Also, instead of copying, walk through preorder with a single moving index (next) and pass the inorder range [lo, hi) for the current subtree. The values are unique, so each value has exactly one position.

Java

import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private int next; // index of the next root in preorder
    private int[] preorder;
    private Map<Integer, Integer> position;

    private TreeNode build(int lo, int hi) { // builds the subtree for inorder[lo, hi)
        if (lo >= hi) {
            return null;
        }
        int val = preorder[next++];
        int mid = position.get(val);
        TreeNode node = new TreeNode(val);
        node.left = build(lo, mid);
        node.right = build(mid + 1, hi);
        return node;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.next = 0;
        this.position = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            position.put(inorder[i], i);
        }
        return build(0, inorder.length);
    }
}

public class Main {
    static String serialize(TreeNode root) {
        if (root == null) {
            return "N";
        }
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        TreeNode tree = s.buildTree(new int[] {3, 9, 20, 15, 7}, new int[] {9, 3, 15, 20, 7});
        System.out.println(serialize(tree));
        System.out.println(serialize(s.buildTree(new int[] {}, new int[] {})));
    }
}

Output

3,9,N,N,20,15,N,N,7,N,N
N

Time: O(n). Space: O(n) for the map, plus O(h) recursion. The left subtree must be built before the right one, because preorder lists the left subtree's nodes first.

Interview points

The first preorder value is the root; its position in inorder splits the left and right subtrees.
Unique values are required so that the position of the root in inorder is unambiguous.
A HashMap of inorder positions removes the linear search, and index ranges remove the array copies.
Build the left subtree before the right one, because next advances through preorder.

Summary

Brute force: O(n²) time from the search and the copies.
Optimal: O(n) time and O(n) space for the map.
Preorder gives the roots in order; inorder gives the subtree boundaries.