Construct Binary Tree From Preorder And Inorder Traversal | Leetcode 105 | codestorywithMIK

In this video we will try to solve “Construct Binary Tree From Preorder And Inorder Traversal”.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Construct Binary Tree From Preorder And Inorder Traversal

Company Tags : Accolite, Amazon, Microsoft

My GitHub Repo for interview preparation : https://
Thank you
#coding #helpajobseeker #easyrecipes
#interviewpreparation #interview_ds_algo #hinglish

[AIsinger]

most underrated channel, I'll definitely post about this channel on linkedin.

[tanujasharma]

watched it twice to understand clearly

[JJ-tpdd]

Java Implementation:

class Solution {

private int idx;

private TreeNode solve(int[] preorder, int[] inorder, int start, int end) {

if(start > end) {
return null;
}

TreeNode root = new TreeNode(preorder[idx]);
int i = start;

for(; i<=end; i++) {
if(inorder[i] == root.val)
break;
}

idx++;

root.left = solve(preorder, inorder, start, i-1);
root.right = solve(preorder, inorder, i+1, end);

return root;
}

public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
idx = 0;

return solve(preorder, inorder, 0, n-1);

}
}

[ayushkumarsingh]

Genuine Doubt Please help
20:34 bhaiya hm log too idx++ kr rhe hai aur jb root->left & root->right mai too idx ka new value jayega too bina pass by reference k galat answer kyu aa rha hai ?

[keertilata]

SLIGHTLY OPTIMIZED APPROACH USING MAP
TreeNode* solve(vector<int>& preorder, vector<int>& inorder, int start, int end, int &idx, map<int, int> &inList ) {
if(start>end){
return NULL;
}
int rootVal = preorder[idx];
int inorderIdx = inList[rootVal];
idx++;
TreeNode* root = new TreeNode(rootVal);

root->left = solve(preorder, inorder, start, inorderIdx-1, idx, inList);
root->right = solve(preorder, inorder, inorderIdx+1, end, idx, inList);

return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int idx = 0;
int n = preorder.size();
map<int, int> inList;
for(int i=0;i<inorder.size();i++){
inList[inorder[i]]=i;
}
return solve(preorder, inorder, 0, n-1, idx, inList);
}

[sauravfarkade]

thanks a lot bhaiya.... sirf story se code likh liya... ;)

[anchalagarwal]

Hi MIK, I was trying your solution for this problem, but I have one issue, when I pass ind+1 for both left and right subtrees, it leads to duplicacy and incorrect results, i am slight confused on how yours was submitted: # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def solve(preorder, inorder, st, end, ind):
if st>end: return None
if ind>=len(preorder): return
rootVal=preorder[ind]
i=st
while i<=end:
if inorder[i]==rootVal:
break
i+=1
root=TreeNode(rootVal)
root.left=solve(preorder, inorder, st, i-1, ind+1)
lefttree=i-st
root.right=solve(preorder, inorder, i+1, end, ind+lefttree+1)
# print(root)
return root
n=len(preorder)
return solve(preorder, inorder, 0, n-1, 0)

[ManaswiRane]

Day 47
Forgot to comment but solved triplet 1 and 2😅

[Lakshya-fl]

Beautiful question and great explanation!!

[AkhileshChouhan-dv]

Bhaiya plz upload recursion playlist with the basics

[basujain]

guys is wale ques vese striver soln jyada samajh aya mujhe

[shadabkalim]

hey, i used the approach from ur latest video of construction of binary tree using postorder and inorder and wrote this but its giving incorrect output:

class Solution {
public:
TreeNode* solve(vector<int>& inorder, vector<int>& preorder, int inStart, int inEnd, int preStart, int preEnd, map<int, int>& inMap) {
if (preStart > preEnd || inStart > inEnd) return NULL;

TreeNode* root = new
int i = inMap[root->val];
int leftSize = i - inStart;

root->left = solve(inorder, preorder, inStart, i - 1, preStart + 1, preStart + leftSize, inMap);
root->right = solve(inorder, preorder, i + 1, inEnd, preStart + leftSize + 1, preEnd, inMap);

return root;
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& preorder) {
int n = inorder.size();
int inStart = 0, inEnd = n - 1;
int preStart = 0, preEnd = n - 1;
map<int, int> inMap;
for (int i = 0; i < n; i++) inMap[inorder[i]] = i;

TreeNode* root = solve(inorder, preorder, inStart, inEnd, preStart, preEnd, inMap);
return root;
}
};


can u pls tell me where i'm wrong? even chatgpt can't figure it out