L34. Construct a Binary Tree from Preorder and Inorder Traversal | C++ | Java

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

Checkout the problem link 👇🏼
Construct a Binary Tree from Preorder and Inorder Traversal | C++ | Java

[takeUforward]

Hi, hope you are well.


Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL and many other time saving features under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing yourself.

[roushankumar]

Free me Aisa explanation koi nii dega. You are real life hero.

[SchrodingerMan]

for those who are getting TLE - pass the map in function with refernce it happens beacause when we pass map without refernce it start to copy all the whereas if we pass the reference it only take base so saving the time :-)

[gouravkumarshaw]

(a) Inorder (Left, Root, Right) :
(b) Preorder (Root, Left, Right) :
(c) Postorder (Left, Right, Root) :

[samyakjain]

coding ninja ka course liya tha usme iski explanation smjh nhi aayi lekin apki video dekhi aur 1 shot me smjh aagai . thanks striver . u teach like u r my friend and not a teacher which i like most bout ur videos !!

[gouravchaki]

Out of all these coding I would just provide method to prepare Biriyani!!
Step 1 Prepare saffron-kewra water and chop veggies
To make a delightful chicken biryani dish, firstly soak saffron in water to prepare saffron water (one tsp saffron can be soaked in 1/4 cup water). Next, mix kewra drops in water and mix well to make kewra water. Set them aside for later usage. Now, chop the onion and coriander leaves and keep them aside.

Step 2 Saute the onions
Meanwhile, heat olive oil in a deep bottomed pan. Once the oil is hot enough, add cumin seeds, bay leaf, green cardamom, black cardamom, cloves in it, and saute for about a minute. Then, add chopped onion to it and saute until pink. Now, add chicken into it with slit green chillies, turmeric, salt to taste, ginger-garlic paste, red chilli powder and green chilli paste. Mix well all the spices and cook for 2-3 minutes. Then, add hung curd into it and give a mix. (Make sure the chicken is washed properly and patted dry before adding it to the dish)

Step 3 Cook biryani on low heat for 5-6 minutes
Turn the flame to medium again and add garam masala in it along with ginger julienned, coriander and mint leaves. Add kewra water, rose water and 1 tsp saffron water in it. Cook till the chicken is tender. Then add 1 cup cooked rice and spread evenly. Then add the remaining saffron water and pour ghee over it. You can now cook the dish without the lid or cover it with a lid to give a dum-effect due to the steam formation.

Step 4 Serve hot chicken biryani with your favourite chutney or raita
Cook for 15-20 minutes with a closed lid and garnish with 1 tbsp fried onions and coriander leaves. Serve hot chicken biryani with raita of your choice. Enjoy!

[Pw_Unfiltered]

coding up this logic is an entire knowledge set needed to be learnt😭😭

[NitishGautam-gj]

Bro we need more teachers like you 😢😢😢 who actually can think from perspective of a beginner and explain step by step

[manaskhare]

It took a while to understand this tricky problem, but now it's completely clear. Thank you striver, kudos for such amazing content.

[curlyone]

I spent two days trying to understand this Algo. Finally, your video made me understand it. Thanks. :)

[xdjqye]

this feels more of a hard level question than a medium level one. but then again, that just might be me since i'm not too familiar with the complexity trees have to offer. anyway, thanks for this amazing explanation. took me over 2 hours to get the hang of it and implement it but the concept feels crystal clear now!

[natanshisharma]

If you are confused how the they are storing addresses, its during backtracking that the nodes addresses are being stored not during creation of the nodes.

[stith_pragya]

UNDERSTOOD...Thank You So Much for this wonderful

[anubhav]

/**
* 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) {}
* };
*/

/*
JUST FINDING THE POSITION OF THE FIRST ELEMENT IN THE PREORDER VECTOR IN THE INORDER VECTOR THEN USING THE POSITION OF THAT ELEMENT TO FIND THE LEFT SUBTREE AND THE RIGHT SUBTREE

*/

class Solution {
public:

int find_pos(vector<int>v, int x){
for(int i=0;i<v.size();i++){
if(v[i]==x)
return i;
}
return -1;
}
TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
if(pre.size()==0)
return NULL;
int pos=find_pos(in, pre[0]);
TreeNode* root=new TreeNode(pre[0]);
vector<int>l1(pre.begin()+1, pre.begin()+pos+1);
vector<int>l2(in.begin(), in.begin()+pos);
vector<int>r1(pre.begin()+pos+1, pre.end());
vector<int>r2(in.begin()+pos+1, in.end());

root->left=buildTree(l1, l2);
root->right=buildTree(r1, r2);

return root;
}
};

[aasutoshbaraiya]

I use different approach like constructing tree step-by-step and splitting inoreder traversal...



class Solution {
public:
bool splitArray(const vector<int>& arr, int target, vector<int>& currLeft, vector<int>& currRight) {
auto it = find(arr.begin(), arr.end(), target);
if (it == arr.end()) return false;

int idx = it - arr.begin();
currLeft.assign(arr.begin(), it);
if (idx + 1 < arr.size()) {
currRight.assign(it + 1, arr.end());
}
return true;
}

TreeNode* subTree(vector<int> leftArr, vector<int> rightArr, vector<int> &preOrder, int &index){
if(index >= preOrder.size()){
return NULL;
}

vector<int> currLeft, currRight;

// spliting leftArr and rightArr for currLeft, currRight
if (!splitArray(leftArr, preOrder[index], currLeft, currRight)) {
currLeft.clear();
splitArray(rightArr, preOrder[index], currLeft, currRight);
}

TreeNode* newNode = new TreeNode(preOrder[index]);
index++;
if(!currLeft.empty()){
newNode->left = subTree(currLeft, {}, preOrder, index);
}

if(!currRight.empty()){
newNode->right = subTree({}, currRight, preOrder, index);
}

return newNode;
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int ind = 0;
TreeNode* root = subTree(inorder, {}, preorder, ind);
return root;
}
};

[ShreyaJain-]

Here is the code to deal with duplicate elements we use a queue so that the element that occurs later in the in-order get pushed at the front and keep popping the index that are processed, we now get a correct tree formed according to the preorder traversal

class Solution{
public:
Node* solve(int in[], int in_start, int in_end, int pre[], int pre_start, int pre_end, map<int, queue<int>> &pos)
{
if(pre_start>pre_end|| in_start>in_end)
{
return NULL;
}
int
pos[pre[pre_start]].pop();
int elem=inroot-in_start;
Node* root=new Node(pre[pre_start]);
root->left=solve(in, in_start, inroot-1, pre, pre_start+1, pre_start+elem, pos);
root->right=solve(in, inroot+1, in_end, pre, pre_start+elem+1, pre_end, pos);
return root;

}

Node* buildTree(int in[], int pre[], int n)
{
// Code here

if(n==0)
return NULL;
map<int, queue<int>> pos;
for(int i=0;i<n;i++)
{
pos[in[i]].push(i);
}
return solve(in, 0, n-1, pre, 0, n-1, pos);
}
};

[ss-pzzh]

THE BEST TREE series even though i have taken a paid course...still i am coming here to understand ...>God Bless u TUF

[roushankumar]

You have changed the teachers image as spreading skill without taking any money❤

[nilesh]

Great explanation as always. The last dry run just before showing code was very very helpful.

[gautamkrishnan]

Keep Going Striver!! I am following your SDE Sheet to revise on the DSA concepts. Thank you so much for all your content.