LeetCode: 105. Construct Binary Tree from Preorder and Inorder Traversal

The Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example

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

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.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> inorderIndexMap;

    for (int i = 0; i < inorder.size(); ++i) 
	    inorderIndexMap[inorder[i]] = i;

    int preorderIndex = 0;

    return buildTreeHelper(
    	preorder, inorder, 
	    preorderIndex, 
    	0, inorder.size() - 1,
	    inorderIndexMap
    );
}

TreeNode* buildTreeHelper(
    vector<int>& preorder, vector<int>& inorder, 
    int& preorderIndex, 
    int left, int right,
    unordered_map<int, int>& inorderIndexMap
) {

    if (left > right) return NULL;

    int rootValue = preorder[preorderIndex];
    TreeNode* root = new TreeNode(rootValue);
    int inorderIndex = inorderIndexMap[rootValue];

    ++preorderIndex;

    root->left = buildTreeHelper(
        preorder, inorder, 
        preorderIndex, 
        left, inorderIndex - 1,
        inorderIndexMap
    );

    root->right = buildTreeHelper(
        preorder, inorder, 
        preorderIndex, 
        inorderIndex + 1, right,
        inorderIndexMap
    );

    return root;
}

Explanation:

• The buildTree function is the entry point for constructing the binary tree. It takes the preorder and inorder vectors as inputs.
• An unordered_map named inorderIndexMap is created to store the indices of values in the inorder array. This map will allow us to quickly find the position of a value in the inorder traversal.
• A for loop iterates through the inorder array to populate inorderIndexMap with values and their corresponding indices.
• The preorderIndex variable is initialized to 0. It keeps track of the current position in the preorder array.
• Finally, the buildTreeHelper function is called with the necessary parameters to construct the binary tree.
• The buildTreeHelper function is a recursive function responsible for constructing a subtree of the binary tree.
• It takes parameters including the preorder and inorder vectors, the preorderIndex (used to track the position in the preorder array), and the left and right indices (indicating the range of values in the current subtree).
• The base case checks if the left index exceeds the right index, in which case it returns NULL to indicate an empty subtree.
• It retrieves the root value from the preorder array and creates a new TreeNode with that value.
• It finds the position of the root value in the inorder array using inorderIndexMap.
• The preorderIndex is incremented to move to the next value in the preorder array.
• The function then recursively constructs the left and right subtrees by adjusting the left and right indices accordingly.
• Finally, it returns the root of the constructed subtree.