In this post, we are going to solve the 105. Construct Binary Tree from Preorder and Inorder Traversal problem of Leetcode. This problem 105. Construct Binary Tree from Preorder and Inorder Traversal is a Leetcode medium level problem. Let’s see code, 105. Construct Binary Tree from Preorder and Inorder Traversal – Leetcode Solution.

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

Now, let’s see the code of 105. Construct Binary Tree from Preorder and Inorder Traversal – Leetcode Solution.

Construct Binary Tree from Preorder and Inorder Traversal – Leetcode Solution

105. Construct Binary Tree from Preorder and Inorder Traversal – Solution in Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public TreeNode buildTree(int[] inorder, int[] preorder,
                              int psi,int pei, int isi, int iei){
        if(isi > iei) return null;   
        
        int idx = isi;
        while(preorder[psi] != inorder[idx]) idx++;
        int dist = idx - isi;
        
        TreeNode node = new TreeNode(preorder[psi]);
        
        node.left = buildTree(inorder,preorder,psi+1,psi+dist,isi,idx-1);
        node.right = buildTree(inorder,preorder,psi+dist+1,pei,idx+1,iei);
        
        return node;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        return buildTree(inorder,preorder,0,n-1,0,n-1);
    }
}

105. Construct Binary Tree from Preorder and Inorder Traversal – Solution in C++

/**
 * 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:
    int preInd=0;
    map<int, int > mp;
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        for(int i = 0 ; i <inorder.size(); i++)
            mp[inorder[i]] =  i;
        return createTree(preorder,inorder,0,inorder.size() - 1);
    }
    TreeNode* createTree(vector<int>& preorder, vector<int>& inorder,int start, int end){
        if(start > end) return NULL;

        TreeNode* node=new TreeNode(preorder[preInd++]);
        int pos =  mp[node->val];

        node->left =createTree(preorder, inorder,start,pos-1);
        node->right =createTree(preorder, inorder, pos+1,end);
        return node;
    }
};

105. Construct Binary Tree from Preorder and Inorder Traversal – Solution in Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, preorder, inorder):
        if not preorder and not inorder:
            return None

        if len(preorder) == 1:
            return TreeNode(preorder[0])

        idx = inorder.index(preorder[0])

        root = TreeNode(preorder[0])
        root.left = self.buildTree(preorder[1:1+idx], inorder[:idx])
        root.right = self.buildTree(preorder[1+idx:], inorder[idx+1:])

        return root
        

Note: This problem 105. Construct Binary Tree from Preorder and Inorder Traversal is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.