Construct Binary Tree from Preorder and Inorder Traversal

Problem

You are given two integer arrays preorder and inorder.

• preorder is the preorder traversal of a binary tree
• inorder is the inorder traversal of the same tree
• Both arrays are of the same size and consist of unique values.

Rebuild the binary tree from the preorder and inorder traversals and return its root.

Examples

Example 1:

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

Output: [1,2,3,null,null,null,4]

Example 2:

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

Output: [1]

Constraints

• 1 <= inorder.length <= 1000.
• inorder.length == preorder.length
• -1000 <= preorder[i], inorder[i] <= 1000

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes.

Solution

We use the preorder list (root, left, right) to perform DFS and create the tree in preorder. The problem is that because we don’t have the nullptrs in our list, we don’t know what nodes belong where in the subtrees. The inorder list gives us that information. If we find the value of a node in inorder, all nodes in the left subtree are to the left of it, and all nodes in the right subtree are to the right of it. There may be unrelated nodes on the left/right as well, so we need to track a search window that limits how far to the left/right of the node in inorder that belong to the left/right subtrees.

We first map the inorder values to the indices, so given a value we can quickly find its index in inorder. We start with an index in preorer starting at 0. Every preorder traversal iteration will increment this. We start with a search window of the entire range of indices (since we are using std::size_t, the right end of the window is exclusive).

Every iteration will get the value from preorder, make a local root node, find its index using the mapping, then set the left/right subtrees through recursion, where the left subtree uses the left window and the right subtree uses the right window.
The best case is when we have a window size of 1 (empty because exclusive indexing on the right window side).

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        std::unordered_map<int, std::size_t> inorder_to_idx;
        for (std::size_t i = 0; i < inorder.size(); ++i) {
            inorder_to_idx[inorder[i]] = i;
        }
 
        std::size_t idx_preorder = 0;
        std::function<TreeNode*(std::size_t, std::size_t)> runner;
        // Create tree using window [l, r)
        runner = [&](std::size_t l, std::size_t r) -> TreeNode* {
            // Base case
            if (l >= r) { return nullptr; }
            auto root_val = preorder[idx_preorder++];
            TreeNode *root = new TreeNode(root_val);
            std::size_t idx_mid = inorder_to_idx[root_val];
            // Everything to left of idx_mid within [l,r) is left subtree
            root->left = runner(l, idx_mid);
            // Everything to right of idx_mid within [l,r) is right subtree
            root->right = runner(idx_mid + 1, r);
            return root;
        };
 
        return runner(0, preorder.size());
 
    }
};