Construct Binary Tree from Preorder and Inorder Traversal

MediumBinary Trees

Rebuild a binary tree from its preorder and inorder traversal arrays, which contain unique values.

Constraints

1 <= nodes <= 3000
Values are unique

Recursive split by root index

Time O(n)Space O(n)

The first preorder value is the root; its position in inorder splits left and right subtrees. A hash map of inorder indices and a moving preorder pointer build the tree in linear time.

#include <bits/stdc++.h>
using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> idx;
    for (int i = 0; i < (int)inorder.size(); i++) idx[inorder[i]] = i;
    int pre = 0;
    function<TreeNode*(int,int)> build = [&](int lo, int hi) -> TreeNode* {
        if (lo > hi) return nullptr;
        int rootVal = preorder[pre++];
        TreeNode* node = new TreeNode{rootVal, nullptr, nullptr};
        int mid = idx[rootVal];
        node->left = build(lo, mid - 1);
        node->right = build(mid + 1, hi);
        return node;
    };
    return build(0, inorder.size() - 1);
}