105. Construct Binary Tree from Preorder and Inorder Traversal

Problem Statement

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 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.

Intuition

Approach:

Maintain two indexes in pre and inorder array
When start crosses end, We stop , elements over

Now What we do is we hash the inorder elements

And notice that

Inorder is Left Root Right
Preorder is Root Left Right

Now We shift the pointers accordingly

Like when we take preorder for next left sub-tree
We take preorder +1 to preorder+no_elements (between inorder start to index of root)

As all the preorder are in line

Links

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Video Links

https://www.youtube.com/watch?v=aZNaLrVebKQ&ab_channel=takeUforward

Approach 1:

C++

class Solution {
public:
    unordered_map<int, int>mp;
    TreeNode* Tree(vector<int>& preorder, int pre_start, int pre_end, vector<int>& inorder, int in_start, int in_end){
        if(pre_start > pre_end or in_start > in_end)
            return nullptr;

        TreeNode *root = new TreeNode(preorder[pre_start]);
        int inRoot = mp[root->val];
        int numsLeft = inRoot-in_start;

        root->left = Tree(preorder, pre_start+1, pre_start+numsLeft, inorder, in_start, inRoot-1);
        root->right = Tree(preorder, pre_start+1+numsLeft, pre_end, inorder, inRoot+1, in_end);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i=0; i<inorder.size(); i++)
            mp[inorder[i]] = i;

        return Tree(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++