Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

Given two integer arrays preorder and inorder, you are required to reconstruct a binary tree. These arrays represent the preorder and inorder traversals of a binary tree, respectively. The preorder array provides the root-first traversal sequence of the tree, while the inorder array offers a left-root-right traversal sequence. Utilizing these two sequences, you are to build and return the binary tree structure that conforms to these traversal orders.

Examples

Example 1

Input:

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

Output:

[3,9,20,null,null,15,7]

Example 2

Input:

preorder = [-1], inorder = [-1]

Output:

[-1]

Constraints

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder and inorder consist of unique values.
• Each value of inorder also appears in preorder.
• preorder is guaranteed to be the preorder traversal of the tree.
• inorder is guaranteed to be the inorder traversal of the tree.

Approach and Intuition

When tackling the problem of reconstructing a binary tree from its preorder and inorder traversal data, it’s crucial to understand the basic properties of these traversals:

• Preorder Traversal:
  • The first element is always the root of the tree.
  • Following the root, the sequence contains nodes from the left subtree, followed by nodes from the right subtree.
• Inorder Traversal:
  • Nodes from the left subtree appear first, followed by the root, and then nodes from the right subtree.

Using the above properties, we can infer the following steps to reconstruct the tree:

1. The first element in the preorder list identifies the root node of the binary tree.
2. Locate this root within the inorder list. The position of this root splits the inorder list into left and right subtrees.
3. Subsequently, use the length of the left subtree determined from the inorder list to split the elements in the preorder list into left and right subtrees.
4. Recursively apply the above steps to construct the left subtree from the left segments of the preorder and inorder lists.
5. Similarly, use the right segments of the lists to recursively construct the right subtree.
6. Proceed with this division and recursive construction until all elements from both arrays are utilized, which completes the tree construction.

The recursion leverages the first element extraction in the preorder array to identify root nodes and uses the root’s index in the inorder array to delineate bounds of left and right subtrees. Since both arrays contain unique values and each value from one also appears in the other, this method reliably constructs the correct binary tree structure.

Solutions

class Solution {
public:
    int currentPreorderIndex = 0;
    unordered_map<int, int> indexMap;
    TreeNode* buildSubTree(vector<int>& preorder, int start, int end) {
        if (start > end) return nullptr;
        int rootVal = preorder[currentPreorderIndex++];
        TreeNode* root = new TreeNode(rootVal);
        root->left = buildSubTree(preorder, start, indexMap[rootVal] - 1);
        root->right = buildSubTree(preorder, indexMap[rootVal] + 1, end);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        currentPreorderIndex = 0;
        for (int i = 0; i < inorder.size(); i++) {
            indexMap[inorder[i]] = i;
        }
        return buildSubTree(preorder, 0, preorder.size() - 1);
    }
};