Construct Binary Tree From Preorder And Inorder Traversal-(Microsoft, Amazon):Live Coding 🧑🏻‍💻

[@AIsinger96]

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

[@codestorywithMIK]

This means a lot ❤️❤️🙏🙏
Feel free to tag me on LinkedIn 😇

[@AIsinger96]

@@codestorywithMIK yes bhaiya

[@killeraloo3247]

Bhai kya hi simple samjhate ho. Sab samajh aa jata hai.

[@aaravmishra3487]

Different approach using 2 indices, one you mentioned in inorder & postorder one!
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, inorder, 0, inorder.length-1, 0, preorder.length-1);
}
public TreeNode buildTree(int[] preorder, int[] inorder, int inStart, int inEnd, int preStart, int preEnd) {
if(inStart > inEnd || preStart > preEnd) return null;
TreeNode root = new TreeNode(preorder[preStart]); // preorder = [3,2,1,4,5], root-> 3 (root, left, right)
int i = inStart;
for(; i

[@codestorywithMIK]

Wonderful.
So glad to see other approaches ❤️

[@keertilata20]

SLIGHTLY OPTIMIZED APPROACH USING MAP
TreeNode* solve(vector& preorder, vector& inorder, int start, int end, int &idx,map &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& preorder, vector& inorder) {
int idx = 0;
int n = preorder.size();
map inList;
for(int i=0;i

[@SaranshKasliwal]

Yeah using map Time-Complexity Will reduce to O(n) instead of O(n^2)

[@JJ-tp2dd]

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

[@surajsidar2294]

My below Java code is not passing example test cases
I compared line by line . It looks same . What is wrong below
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int idx = 0;
return helper(preorder, inorder, 0, preorder.length - 1, idx);
}
TreeNode helper(int[] preorder, int[] inorder, int start, int end, int idx) {
if (start > end)
return null;
int rootValue = preorder[idx];
int i = start;
for (; i

[@abhayroadlines528]

@@surajsidar2294 keep your variable "idx" out of the function.

[@sauravfarkade7032]

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

[@monjuralam7346]

in the optimized version, no need to pass the inorder arry; we already have a map
TreeNode* construct(vector& preorder, int l, int r, int& idx) {

[@aayushranjan5572]

bhaiya pls recursion padha do na us playlist me bus leetcode ke que sol krna plssssssssssss

[@muskanyadav8660]

great explanation...

[@Lakshya-f4l]

Beautiful question and great explanation!!

[@venkatarohitpotnuru38]

Super bhaiyya

[@aditgulia]

bal baccha karna hoga was epic line hahaha... btw nice explaination

[@basujain8928]

guys is wale ques vese striver soln jyada samajh aya mujhe

[@codestorywithMIK]

Really glad to know you understood the solution , be it from any resource 😇❤️
And definitely I would be glad if you can share improvements or feedbacks.

[@rdrahuldhiman19]

Amazing man, thanks again.

[@codeandtalk6]

❤

[@shadabkalim9102]

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& inorder, vector& preorder, int inStart, int inEnd, int preStart, int preEnd, map& inMap) {
if (preStart > preEnd || inStart > inEnd) return NULL;
TreeNode* root = new TreeNode(preorder[preStart]);
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& inorder, vector& preorder) {
int n = inorder.size();
int inStart = 0, inEnd = n - 1;
int preStart = 0, preEnd = n - 1;
map 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

[@shadabkalim9102]

i figured out the error, it was a really silly mistake

[@pixelpixel1977]

Why we need to pass the idx as pass by reference? Can someone please explain this once??

[@surajsidar2294]

There is need of pass by refernce.
If you write same code in Java it won't work.
Unlike C++ there is no pass by reference in Java , so there is need to create global variable idx.
Below was my code in Java which didn't work
class Solution {
//int idx;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int idx = 0;
return helper(preorder, inorder, 0, preorder.length - 1,idx);
}
TreeNode helper(int[] preorder, int[] inorder, int start, int end,int idx) {
if (start > end)
return null;
int rootValue = preorder[idx];
int i = start;
for (; i

[@PushpendraKushvaha]

@@surajsidar2294 Even mine is not working, have you find the solution for the same.

[@Paul-ih8lj]

If you don't pass it by reference, by default it'll be passed by value i.e each the recursive function gets called it'll be reset. By passing by reference you are able to remember the previous idx value.