This was a great video. However it would be more helpful if you could also share the intuition or the idea or the thought process behind developing a solution instead of only explaing it with the dry run of the code. That way we will be able to develop the thinking process to tackle any similar questions in future.
To all who thinks why recursion is not used instead of this little complex code i will like to tell the thing that there will be many instances where we need to apply some constraints while using these algorithms to get desire output which may not be got by using recursive method thats why iterative way is important ig.
We can simply use recursion as well: void trav(BinaryTreeNode *root,vector &in, vector &pre, vector &post){ if(!root) return; pre.push_back(root->data); trav(root->left, in, pre, post); in.push_back(root->data); trav(root->right, in, pre, post); post.push_back(root->data); }
@@vedansh4033 recursion one we can do ourselves, so I guess that's why he covered iterative one. recursion is literally magic and more intuitive than these iterative solns.
If anyone who doesn't understand the meaning of &..... Here we are updating the original vectors which are passed as arguments while calling the function. It's a concept of shared memory (reference) in C++. Happy to Help 🙋♂️
I have one suggestion that helped me understand this algorithm better. Change pair from int to string, and set "preOrder", "inOrder", "postOrder" in place of 1,2,3. #include #include #include using namespace std; struct Node { int data; struct Node *l, *r; Node(int val) { data = val; l = r = NULL; } }; void printTree(vector nodeArray) { int n = nodeArray.size(); for (int i = 0; i < n; i++) { cout l != NULL) { st.push({ it.first->l, "preOrder" }); } } else if (it.second == "inOrder") { inOrder.push_back(it.first->data); it.second = "postOrder"; st.push(it); if (it.first->r != NULL) { st.push({ it.first->r, "preOrder" }); } } else { postOrder.push_back(it.first->data); } } printTree(preOrder); printTree(inOrder); printTree(postOrder); } int main() { struct Node* root = new Node(1); root->l = new Node(2); root->r = new Node(3); root->l->l = new Node(4); root->l->r = new Node(5); root->l->r->l = new Node(6); root->r->l = new Node(7); root->r->r = new Node(8); root->r->r->l = new Node(9); root->r->r->r = new Node(10); preInPostTraversal(root); cout
‘auto’ means, the type of this variable will be decided dynamically. In this case, in place of auto one would write “pair it = st.top()” to get the same result.
Hey, really hats off to you for this approach. I have two questions, this could be very easily done using recursive approach right? And also what is the intuition of this idea? Like How did you land up here or what made you think of an approach this way?
for preorder(we print the node when we touch for the first time,before touching left and right node),for inorder we print the node when we touch it for second time(after touching left node),for post order we print the node when we meet it for third time(after meeting left and right)..
take a tree with 3 nodes and apply pre,in and post order..see when we are printing the node for each traversal....Intution here is after how many visits we are printing the node.....(assume each node as a root node)
Rather than poping out from stack in all the cases, we can rather do, (st.top().second++) in case of number being 1 or 2. And if number is 3 then we can do st.pop() Bhaiya Please correct me if I am wrong..
if anyone is thinking that this is problmatic no its not just view this last one and this video from upar upar and move on...aage ka content tagda haii...yhi pr tree pr mat ruk jana...prsnl experince
We can also separate the code for individual traversals: PRE ORDER: class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root:return stack=[[root,1]] preorder=[] while stack: curr=stack.pop() if curr[1]==1: preorder.append(curr[0].val) curr[1]+=1 stack.append(curr) if curr[0].left: stack.append([curr[0].left,1]) elif curr[1]==2: curr[1]+=1 stack.append(curr) if curr[0].right: stack.append([curr[0].right,1]) return preorder IN ORDER: class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root:return stack=[[root,1]] inorder=[] while stack: curr=stack.pop() if curr[1]==1: curr[1]+=1 stack.append(curr) if curr[0].left: stack.append([curr[0].left,1]) elif curr[1]==2: inorder.append(curr[0].val) curr[1]+=1 stack.append(curr) if curr[0].right: stack.append([curr[0].right,1]) return inorder POST ORDER: class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root:return stack=[[root,1]] postorder=[] while stack: curr=stack.pop() if curr[1]==1: curr[1]+=1 stack.append(curr) if curr[0].left: stack.append([curr[0].left,1]) elif curr[1]==2: curr[1]+=1 stack.append(curr) if curr[0].right: stack.append([curr[0].right,1]) else: postorder.append(curr[0].val) return postorder
just take a tree of 3 node. think if u visit 1st time its pre.then after printing 1as pre u moves to lleft so that left will be printed and u can came back and print 1 as in. after that print 1 as inorder u moves to right. So just as u visit 1st time putting it in preorder and telling in second visit 1 is used as inorder.
No need to pop and push again in cases 1 and 2 : From where did you get this algorithm? Any ways thank you!! public List preOrder(TreeNode root, List op) { if(root == null) return op; Stack stack = new Stack(); Pair start = new Pair(root, 1); stack.push(start); while(!stack.isEmpty()) { Pair p = stack.peek(); if(p.order == 1) { op.add(p.node.val); if(p.node.left != null) { Pair p1 = new Pair(p.node.left, 1); stack.push(p1); } p.order = 2; } else if(p.order == 2) { if(p.node.right != null) { Pair p1 = new Pair(p.node.right, 1); stack.push(p1); } p.order = 3; } else if(p.order == 3) { stack.pop(); } } return op; }
# For Python peeps class BinaryTreeNode : def __init__(self, data) : self.data = data self.left = None self.right = None def getTreeTraversal(root): if not root: return [] pre_order,in_order,post_order=[],[],[] stack=[[root,1]] # adding [node,index] to stack while stack: working_item=stack[-1] if working_item[1]==1: pre_order.append(working_item[0].data) stack[-1][1]+=1
if working_item[0].left: stack.append([working_item[0].left,1]) elif working_item[1]==2: in_order.append(working_item[0].data) stack[-1][1]+=1
if working_item[0].right: stack.append([working_item[0].right,1]) else: post_order.append(working_item[0].data) del stack[-1] return [in_order,pre_order,post_order]
# # another approach , tle score: 34.8/40 # if not root: # return [[],[],[]] # l=getTreeTraversal(root.left) # r=getTreeTraversal(root.right) # return [l[0]+[root.data]+r[0],[root.data]+l[1]+r[1],l[2]+r[2]+[root.data]]
How can someone come up with this intuition? I could relate it to the arrow method, but any help or any suggestions how to develop this without any video??
Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79
everything is right but writing Pair in" Stack st= new Stack()" giving error in intelliJ IDE.
@@amarjeetkumar-hk2jl Where is the link of this problem? Is it not available on Leetcode.
Hattss off to you man !! 😄🎩
i don't know how we can use num for pair in java, because i am getting it as getValue() method, can someone help me about this
If someone dosn't watch the tutorial , i don't think he will be able come up with such an approach in the interview .
exactly
i think all these data structures took a lot of try and error and time to develop
This was a great video.
However it would be more helpful if you could also share the intuition or the idea or the thought process behind developing a solution instead of only explaing it with the dry run of the code. That way we will be able to develop the thinking process to tackle any similar questions in future.
idhar udhar se maaal uthae ga to aise hoga
@@suar_pilla apne name thik rakhe ho akdm😮
@@suar_pilla 😂😂😂exactly to the point
To all who thinks why recursion is not used instead of this little complex code i will like to tell the thing that there will be many instances where we need to apply some constraints while using these algorithms to get desire output which may not be got by using recursive method thats why iterative way is important ig.
I found this much easier than other 3 iterative versions.
true
+1
same here, the intuition was very easy to grasp.
true lol
Bhai job lagi??? 2 saal hogye codeforces ki rating???
We can simply use recursion as well:
void trav(BinaryTreeNode *root,vector &in, vector &pre, vector &post){
if(!root) return;
pre.push_back(root->data);
trav(root->left, in, pre, post);
in.push_back(root->data);
trav(root->right, in, pre, post);
post.push_back(root->data);
}
I was thinking about this in whole video ,, so that's why i can't get what video is all about 🥲🥲🥲🥲
sahi baat hai, pata nahi itna complicate kyo kiya
@@vedansh4033 recursion one we can do ourselves, so I guess that's why he covered iterative one. recursion is literally magic and more intuitive than these iterative solns.
Woahhhhh thanx man
If anyone who doesn't understand the meaning of &..... Here we are updating the original vectors which are passed as arguments while calling the function.
It's a concept of shared memory (reference) in C++.
Happy to Help 🙋♂️
This approach blews my mind....
What?? This is cool man! My college could never!!!!!! Striver thanks for putting light on such solutions. You're just awesome!
This was Amazing. Didn't expected a solution with this level of simplicity :) . Maza aaya!
What a great approach 👏🏽👏🏽, haven't seen this anywhere
Hats off to the approach, stunningly explained 😍
Where is the link of this problem? Is it not available on Leetcode.
@@imshivendra it is on codestudio
I have one suggestion that helped me understand this algorithm better. Change pair from int to string, and set "preOrder", "inOrder", "postOrder" in place of 1,2,3.
#include
#include
#include
using namespace std;
struct Node {
int data;
struct Node *l, *r;
Node(int val) {
data = val;
l = r = NULL;
}
};
void printTree(vector nodeArray) {
int n = nodeArray.size();
for (int i = 0; i < n; i++) {
cout l != NULL) {
st.push({ it.first->l, "preOrder" });
}
}
else if (it.second == "inOrder") {
inOrder.push_back(it.first->data);
it.second = "postOrder";
st.push(it);
if (it.first->r != NULL) {
st.push({ it.first->r, "preOrder" });
}
}
else {
postOrder.push_back(it.first->data);
}
}
printTree(preOrder);
printTree(inOrder);
printTree(postOrder);
}
int main()
{
struct Node* root = new Node(1);
root->l = new Node(2);
root->r = new Node(3);
root->l->l = new Node(4);
root->l->r = new Node(5);
root->l->r->l = new Node(6);
root->r->l = new Node(7);
root->r->r = new Node(8);
root->r->r->l = new Node(9);
root->r->r->r = new Node(10);
preInPostTraversal(root);
cout
What is this auto mean " auto it = st.top(); " ?
‘auto’ means, the type of this variable will be decided dynamically. In this case, in place of auto one would write “pair it = st.top()” to get the same result.
@@kathanvakharia okii thanks ✌️
Striver, this was not much difficult. Understood this properly and took notes as well.
@@gautham7244 wtf. 😂
Sure but, Coming up on your own is ig
I never seen an approach like this 🔥🔥🔥
Recursive is much easier
void trans(TreeNode* root, vector&inorder, vector&postorder, vector&preorder ){
if(root == NULL)
return;
preorder.push_back(root->val);
trans(root->left, inorder,postorder,preorder);
inorder.push_back(root->val);
trans(root->right, inorder, postorder, preorder);
postorder.push_back(root->val);
}
UNDERSTOOD...Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
I love the content ❤.the man behind a successful coder.
Salute to this man 🙏❤🎉
Just too good you are! Keep making the great content and thanks.
Where is the link of this problem? Is it not available on Leetcode.
the return type of the function in the c++ code should be void instead of vector just a little correction
I don't know this approach it is amazing thanks Bro for the amazing video
I have watched many of your lectures, but this is the first one where I couldn't understand the intuition behind the code!!
This is a great video, You playlists are really helping us a lot.
Understood! So wonderful explanation as always, thank you very much!!
Where is the link of this problem? Is it not available on Leetcode.
This approach blew my whole mind to pieces ❤️🔥❤️🔥 thanks raj
It's easier than all other traversals❤️❤️💐💐
great work, and have lots of sponsor ad so that you can provide great videos.
Maza agya, perfect last video to consolidate all the concepts of traversals.
This is a really nice concept. All in one. thanks
Completed 14/54(25% done) !!!
please do like the video if u get some value out of it. This is priceless❤
It was worth watching bro...Awesome approach
1:00 - 3:25
edoc urhtlklaw: 8:55
Hey, really hats off to you for this approach. I have two questions, this could be very easily done using recursive approach right? And also what is the intuition of this idea? Like How did you land up here or what made you think of an approach this way?
for preorder(we print the node when we touch for the first time,before touching left and right node),for inorder we print the node when we touch it for second time(after touching left node),for post order we print the node when we meet it for third time(after meeting left and right)..
take a tree with 3 nodes and apply pre,in and post order..see when we are printing the node for each traversal....Intution here is after how many visits we are printing the node.....(assume each node as a root node)
@@bharathkumar5870 You got this from recursive approach right? That is also how I thought, but couldn't have been able to do it iteratively.
@@bharathkumar5870 nice intuition loved it !!
@@bharathkumar5870 Thank you so much Bharath.
woahhh whataa approchhh😧😧😧😳😳😳
Very elegantly done 👍
Rather than poping out from stack in all the cases, we can rather do, (st.top().second++) in case of number being 1 or 2. And if number is 3 then we can do st.pop()
Bhaiya Please correct me if I am wrong..
Absolutely Correct
dont you think,that makes it little complex
if anyone is thinking that this is problmatic no its not just view this last one and this video from upar upar and move on...aage ka content tagda haii...yhi pr tree pr mat ruk jana...prsnl experince
Badiya Advice Bhai!
Same experience with me!
so basically in a pair the left part is termed as first and the second part separated by comma is called second in cpp?
yes
Thank you so much sir
Very well explained. Thank you is a small word.
This video is a gem 💎
Should we cramming this algorithm or try to understand intuition behind it???
Great explanation 🔥🔥🔥🔥
More Simple Code ( Similar to Striver )
void All_in_one_traversal(node* root)
{
if(root==nullptr)
return;
stack s;
vector pre, post,in;
s.push({root,1}); // Push Root Element with Count = 1
while(!s.empty())
{
auto it = s.top();
if(it.second==1) // PREORDER
{
pre.push_back(it.first->data);
s.top().second = 2;
if(it.first->left != nullptr)
s.push({it.first->left,1});
}
else if(it.second==2) // INORDER
{
in.push_back(it.first->data);
s.top().second = 3;
if(it.first->right != nullptr)
s.push({it.first->right,1});
}
else if(it.second==3) // POSTORDER
{
post.push_back(it.first->data);
s.pop();
}
}
// Printing Pre-Order
for(int i=0; i
We can also separate the code for individual traversals:
PRE ORDER:
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:return
stack=[[root,1]]
preorder=[]
while stack:
curr=stack.pop()
if curr[1]==1:
preorder.append(curr[0].val)
curr[1]+=1
stack.append(curr)
if curr[0].left:
stack.append([curr[0].left,1])
elif curr[1]==2:
curr[1]+=1
stack.append(curr)
if curr[0].right:
stack.append([curr[0].right,1])
return preorder
IN ORDER:
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:return
stack=[[root,1]]
inorder=[]
while stack:
curr=stack.pop()
if curr[1]==1:
curr[1]+=1
stack.append(curr)
if curr[0].left:
stack.append([curr[0].left,1])
elif curr[1]==2:
inorder.append(curr[0].val)
curr[1]+=1
stack.append(curr)
if curr[0].right:
stack.append([curr[0].right,1])
return inorder
POST ORDER:
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:return
stack=[[root,1]]
postorder=[]
while stack:
curr=stack.pop()
if curr[1]==1:
curr[1]+=1
stack.append(curr)
if curr[0].left:
stack.append([curr[0].left,1])
elif curr[1]==2:
curr[1]+=1
stack.append(curr)
if curr[0].right:
stack.append([curr[0].right,1])
else:
postorder.append(curr[0].val)
return postorder
Loved the solution
Sir, if possible, plzz make a video on morris traversals as well. Much needed
At the last..
@@takeUforward thank u sir
Thank you bhaiya for making such a fabulous series
Great Explanation 🔥🔥🔥🔥
Great Approach and Great Explanation!
What is the name of the leetcode problem for this? Can you provide a link for that ?
very nice explanation bro... much appreciated
best as always... thnks
wanted to know if the intuition behind this code is needed to understand or if we need to mug up
same ? did u got the intution?
just take a tree of 3 node. think if u visit 1st time its pre.then after printing 1as pre u moves to lleft so that left will be printed and u can came back and print 1 as in. after that print 1 as inorder u moves to right.
So just as u visit 1st time putting it in preorder and telling in second visit 1 is used as inorder.
@@mayanksingh5783 perfect dude. thanks
Understood ❤
Thankyou so much striver
Awesome approach and explanation
The links in the description for the problem link and cpp code link are not of this question. Please look into it.
Okayy
Nicely Explained..
@take U forward ...what is the intitution behind this ? was it a predefined algorithm or u have to think about such intutuion on the spot!!
It was pre-defined, pretty tough to come up with such hacks
Understood. Thanks a lot.
This one is better than any other traversal.
op bhai bhot accha explain kia
Striver bhaiya, can we give this approach to interviewer for postorder with 1 stack? Like not push__back in pre and inorder arrays? Please reply.
completed lecture 13 of Tree Playlist.
What is better to use....... iterative or recursive method?
I watched it, I understood it but I think if I'll try it after some time, I won't be able to do it, so should I cram this?
OP bhaiya🔥🔥 maza aa gaya:)
should we learn traversing through iteration and recursion both ?
mazzaaa hii agya bhaiaa ye dekh kar
the problem link is taking to level order traversal its not taking to the question which was discussed in the video
Let me update
@@takeUforward Bhaiya till now it is not updated ,we can't find the problem link.
Thank you Bhaiya
What is the intutition behind this approach?
No need to pop multiples times just pop one time in the postorder condition only !!
true
thanks sir
in the website.. the question link linked is of postorder traversal and not this question
No need to pop and push again in cases 1 and 2 :
From where did you get this algorithm? Any ways thank you!!
public List preOrder(TreeNode root, List op) {
if(root == null) return op;
Stack stack = new Stack();
Pair start = new Pair(root, 1);
stack.push(start);
while(!stack.isEmpty()) {
Pair p = stack.peek();
if(p.order == 1) {
op.add(p.node.val);
if(p.node.left != null) {
Pair p1 = new Pair(p.node.left, 1);
stack.push(p1);
}
p.order = 2;
}
else if(p.order == 2) {
if(p.node.right != null) {
Pair p1 = new Pair(p.node.right, 1);
stack.push(p1);
}
p.order = 3;
}
else if(p.order == 3) {
stack.pop();
}
}
return op;
}
Amazing ❤️🔥
THank you so much!
Till now, the question link has not been updated. Can anyone provide the question link of any website?
Bhaiya kindly add the intuition as well.
I mean how can anybody come up with such a solution on their own in the interview.
# For Python peeps
class BinaryTreeNode :
def __init__(self, data) :
self.data = data
self.left = None
self.right = None
def getTreeTraversal(root):
if not root:
return []
pre_order,in_order,post_order=[],[],[]
stack=[[root,1]] # adding [node,index] to stack
while stack:
working_item=stack[-1]
if working_item[1]==1:
pre_order.append(working_item[0].data)
stack[-1][1]+=1
if working_item[0].left:
stack.append([working_item[0].left,1])
elif working_item[1]==2:
in_order.append(working_item[0].data)
stack[-1][1]+=1
if working_item[0].right:
stack.append([working_item[0].right,1])
else:
post_order.append(working_item[0].data)
del stack[-1]
return [in_order,pre_order,post_order]
# # another approach , tle score: 34.8/40
# if not root:
# return [[],[],[]]
# l=getTreeTraversal(root.left)
# r=getTreeTraversal(root.right)
# return [l[0]+[root.data]+r[0],[root.data]+l[1]+r[1],l[2]+r[2]+[root.data]]
much useful
How can someone come up with this intuition? I could relate it to the arrow method, but any help or any suggestions how to develop this without any video??
Great Work
Why cant we do this using recursion?
Like This:
void traversal(BinaryTreeNode *root, vector &pre, vector &in, vector &post)
{
if(root==NULL)
{
return ;
}
pre.push_back(root->data);
traversal(root->left, pre, in, post);
in.push_back(root->data);
traversal(root->right, pre, in, post);
post.push_back(root->data);
}
vector getTreeTraversal(BinaryTreeNode *root)
{
vector ans;
vector pre;
vector in;
vector post;
traversal(root, pre, in, post);
ans.push_back(in);
ans.push_back(pre);
ans.push_back(post);
return ans;
}
Mind-boggling 🧐
Huge respect...❤👏
Thanks
Wowww❤
totally understood thankyouuu so much !!
Thank you sir.
Thank you very much.
UNDERSTOOD;
UNDERSTOOD
FInally, something I can remember.
🙏🙏🙏🙏
I didn't find any practice problem. Is it asked in interviews?
Code studio link
@@takeUforward But that is level order traversal question.
bahut pyaara
Took time to solve, but did. Thankyou Striver!
awesome approach!