Build Tree Postorder and Inorder | C++ Placement Course | Lecture 27.4
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- Complete C++ Placement Course (Data Structures+Algorithm) : • C++ Full Course | C++...
Telegram: t.me/apnikaksh...
Instagram: / dhattarwalaman
Notes of this Lecture:
The reason that right node of current is being built first (than left node ) is that while decrementing from post order array's end we get the right element of the node only , as Postorder follows left right root sequence , so first make right node than left node.
why did she use 'static' in that line static int index=0 ???
@@sayonika254 so that it does not reinitialise itself to 0 again and again during function calls
nice mjja aaya
Thank You.
This sister was so eloquent and articulate in what she says.
It has become so much easier to comprehend the concepts of binary tree.
Contrarily, that guy who appeared in the previous videos was the worst(so hasty in my sense).
I suggest to make her permanent for teaching the tutorials.
indeed brother
here is the source code for reference purpose:
#include
using namespace std;
class Node
{
public:
int data;
Node *right;
Node *left;
Node(int val)
{
data = val;
right = NULL;
left = NULL;
}
};
int search(int inorder[], int start, int end, int val)
{
for (int i = start; i end)
{
return NULL;
}
int val = postorder[idx];
idx--;
Node *curr = new Node(val);
if (start == end)
{
return curr;
}
int pos = search(inorder, start, end, val);
curr->right = maketree(postorder, inorder, pos+1, end);
curr->left = maketree(postorder, inorder, start, pos-1);
return curr;
}
void print_inorder(Node *root)
{
if (root == NULL)
{
return;
}
print_inorder(root->left);
cout data right);
}
int main()
{
int postorder[] = {4, 2, 5, 3, 1};
int inorder[] = {4, 2, 1, 5, 3};
Node *root = maketree(postorder, inorder, 0, 4);
print_inorder(root);
return 0;
}
#include
using namespace std;
class Node
{
public:
int data;
Node* left;
Node* right;
Node(int val)
{
data=val;
left=NULL;
right=NULL;
}
};
int search(int inorder[],int start,int end,int val)
{
for (int i = start; i end)
{
/* code */
return NULL;
}
int val=postorder[idx];
idx--;
Node* curr = new Node(val);
if (start==end)
{
/* code */
return curr;
}
int pos = search(inorder,start,end,val);
curr->right=buildtree(postorder,inorder,pos+1,end);
curr->left=buildtree(postorder,inorder,start,pos-1);
return curr;
}
void inorderPrint(Node* root)
{
if (root==NULL)
{
/* code */
return;
}
inorderPrint(root->left);
cout
i have a error pls solve it
@@faizansaqeeb3390 what error?
@@sleepypanda7172 it is executed.. But not showing output
@@faizansaqeeb3390 paste your code here
code for reference
#include
using namespace std;
struct Node{
int data;
struct Node* left;
struct Node* right;
Node(int val){
data=val;
left=NULL;
right=NULL;
}
};
void printPostorder(struct Node* node){
if(node==NULL)return;
printPostorder(node->left);
printPostorder(node->right);
coutleft->right=new Node(5);
root->right->left=new Node(6);
root->right->right=new Node(7);
int postorder[]={4,5,2,6,7,3,1};
int inorder[]={4,2,5,1,6,3,7};
struct Node* node=buildTree( postorder, inorder, 0, 6);
cout
actualy the start==end is not required , it will automatically be staisfied by base condn
8:55 Just write end instead of 4. We are passing end in buildTree
end pointer lies only in inorder not in postorder .
We are initializing a static variable so used 4
isn't there is mistake in first 30 sec? she said post order definition wrong or am I interpreting it wrong?
can be tiny human error though. Btw explanation was great!! absolutely loving the course
yes she got confused and told inorder def for postorder
Yes ur r right
exactly.
Yes I also noticed that mistake
Thankyou bhaiya and team AB TO PHODENGE
13:05 Why order is changed, rule of Postorder is (Left, Right, Root)
but here we first travel right side and then left in recursive??
Anyone know??
00:15 Slight mistake. Postorder definition.
haa na mujhe bhi laga. Tiny human error
Remember C++ Guys...
Pass postorder & inorder by reference in your function call, otherwise there may be TLE because of several copies creation of post and inorder sequence in successive recursive calls.
I literally learnt this in college rn.
Which year
@@shivamverma3777 Year 1
@@vivekmathur3068 C++ in 1st year in college ?
They didnt teach us the algo and code though
@@apoorvo12 I am not in a college that follows the IIT curricula. We don't spend the first year doing general studies.
leetcode 106 /**
* 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:
unordered_mapin;
public:
TreeNode* helper(vector& inorder, vector& postorder,int start,int end,int &index){
if(start>end) return nullptr;
int curr=postorder[index--];
TreeNode* ele=new TreeNode(curr);
int pos=in[curr];
if(start==end) return ele;
ele->right=helper(inorder,postorder,pos+1,end,index);
ele->left=helper(inorder,postorder,start,pos-1,index);
return ele;
}
TreeNode* buildTree(vector& inorder, vector& postorder) {
int index=inorder.size()-1;
for(int i=0;i
It will be more easier to comprehend if u upload notes.
#include
//#include"Binarytree.h"
#include
using namespace std;
int Search(int inorder[],int l,int e,int cur)
{
for(int i=l;iinorderE)
return NULL;
idx--;
BinaryTreeNode*root=new BinaryTreeNode(cur);
if(inorderS==inorderE)
return root;
int pos=Search(Inorder,inorderS,inorderE,cur);
root->right=buildTree(Postorder,Inorder,pos+1,inorderE);
root->left=buildTree(Postorder,Inorder,inorderS,pos-1);
return root;
}
void print(BinaryTreeNode*root)
{
if(root==NULL)
return ;
queue pendingnodes;
pendingnodes.push(root);
while(!pendingnodes.empty())
{
BinaryTreeNode* front=pendingnodes.front();
cout
Here,is the code for reference purpose.
I have additionally created a funtion to print the original tree in levelwise manner
@@AlokSingh-jw8fr thanks mate :)
@@hardiknegi7066 Don't forget to change the name of class as per your class name
in this approach searching are complete in O(n^2) but it will be optimize by using unordered set or hash table this course is only for your understanding not for gurrented placement course
amazing
very nice teacher!
4:21. plz correction postorder tree mein sbse phle left subtree ko build krte hai.
yes
#include
using namespace std;
struct Node
{
int data;
Node* left;
Node* right;
Node(int val)
{
data = val;
left = NULL;
right = NULL;
}
};
void inorder(Node* root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
cout right = buildTree(ino, post, pos + 1, end);
curr->left = buildTree(ino, post, start, pos - 1);
return curr;
}
int main()
{
int post[] = {4,2,5,3,1};
int ino[] = {4,2,1,5,3};
Node* root = buildTree(ino, post, 0, 4);
inorder(root);
return 0;
}
Can someone tell me why am I getting overflow exception at Node* curr = new Node(val);
Ur struct Node is not correct ,you have to write struct Node* left ;
And
struct Node* right ;
while defining the pointers..
All I can do
Is to say "Shukriyaa"
Thanks a lot🔥🔥
nice work guys
thank you so much
15:56 -> 16:15
Full aur complete konsa statement correct hai bhaiyya.
Please consider any reply
in build tree function why we take idx as 4
7:46
Thank you 🙏🙏
th-cam.com/video/enbdzJhjPgE/w-d-xo.html !
the above code is for a fixed size ,what should we do for passing different cases
not able to print the output, whenever im trying to print blank screen appears
Didi mujhe tree data structures k algorithm approach m bhot dikkat aa rha h 😭 maine ye playlist dekha mujhe smjh bhi aaya lkin jb mai trees.k different questions bnata hu toh logical approach nhi kr paa rhe
watch aditya verma's video. He made a simple common approach for all BT question. & yeah take a moment to practice basic recusrion otherwise you won't be able to solve it you are weak in recursion
i was so confused till 5:19 cuz of the postorder, thinking whatever i learnt till now was useless. Shouldve put a message in the video saying that there was an error in the sequence
yes i am also confused .....can u please explain it
@@NormieCyrox I recommend you search for another video on this topic bro
One doubt:
In line 32: created an object not a pointer, then how come in line 38 & 39 we are using '->' not dot operator?
watch full video there was an error and she corrected
Premiere📍
Fun fact:- if run this recursion without base condition , it would still run properly...
No, it is not working. If you remove start> end condition.
//program to construct tree using postorder and inorder
#include
using namespace std;
class node{
public:
int data;
node*left;
node*right;
};
node* newNode(int data)
{
node *Node=new node();
Node->data=data;
Node->left=NULL;
Node->right=NULL;
return(Node);
}
int search(int in[],int start,int end,int value)
{
for(int i=start;iend)
{
return NULL;
}
node* tnode=newNode(post[postindex]);
postindex--;
/*int val=post[postindex];
postindex--;
node *tnode=newNode(val);*/
if(start==end)
{
return(tnode);
}
int inIndex=search(in,start,end,tnode->data);
tnode->right=buildtree(post,in,inIndex+1,end);
tnode->left=buildtree(post,in,start,inIndex-1);
return(tnode);
}
void preorder(node *root)
{
if(root==NULL)
{
return;
}
else{
cout
please help
@@ankushverma8334 what happened?
Notes kb upload honge
Where are the notes of this lecture?
why did she use 'static' in that line static int index=0 ???
Thanku Soo Much Bhaiya Ji and Faculties Members ;) :)
can't we initialize idx by end. 8:52
Yes , its possible ig
no because we call start and end recursively also then we changes values by pos+1 or pos-1;
We can do that also.
@@HARSHAGRAWALBCE-nb3gb idx variable is static, it initializes only one time i.e. in the first recursive call.
@@gauravupreti9340 yes
static ka use kyu h
uske bina error kyu de rha h code
can anybody tell
@Apna College
taki hr bar function dubara call krne pr wapis se 0 na ho jae
what is complete binary tree ??
Jismein sabhi elements ke child elements 2 ho except last level
Didi at 0:32 u made a mistake in defining Postorder
Plz Edit It
root->message = "Thanks Apni Team"
What are the first 8 lines of this code can anyone help me?
It's is construction of Node structure
@@TripleAYT thanks man i got it
Company direct ask you write algorithm of this code then you write the step how a code start and end...
static int idx = 4 . But why. don't we have to put its value acc. to its size?
Yeah, static int idx = end; will work.
@@parthmittal5625 thanks
Apparently it is n-1
Bro can u plz help me i am getting the reversed inorder sequence in output
@@parthmittal5625 though it does not work as star and end changes when we call recursively end =pos-1 or pos+1 for left and right subtree thats why it deos not help hope you get my point
at 4:24 why postorder sequence has changed ????
It's just a graphical mistake, the order will remain as it was before
aapki awaaz boht pyari hai
so much confusing explanation
😵💫😵💫😵💫😵💫😵💫
Ma panner khaunga
animation se acha board pe btate to jada smjh me ata
kahi aur ja ke padh le
animation se bhi teko samjh nahi aa rha to kya he bole ab, maha Dumb hai tu fir
bhaiyya is giving best content seekhna aana chahiye . pravachan ki tarah dekho ge to toh seekh liye fir
Bhai java ? Bhai piz
Bhaiya yeh C++ ke lectures baad mai dalna pehle please organic ke lectures daldo and modern physics ke notes bhi upload karo
Please bhaiya bahut tension hai muje papers ki
Sirf aap hi sahara ho mera
Please bhaiya, help me
Mai apse request karta hun
#include
using namespace std;
class Node
{
public:
int data;
Node* left;
Node* right;
Node(int val)
{
data=val;
left=NULL;
right=NULL;
}
};
int search(int inorder[],int start,int end,int curr)
{
for(int i=start;iend)
return NULL;
static int indx=6;
int curr= postorder[indx];
indx--;
Node* node=new Node(curr);
if(start==end)
return node;
int inorderpos= search(inorder,start,end,curr);
node->right=buildTree(postorder,inorder,inorderpos+1,end);
node->left= buildTree(postorder,inorder,start,inorderpos-1);
return node;
}
void inordertraversal(Node* root)
{
if(root==NULL)
return;
inordertraversal(root->left);
cout