L13. Preorder Inorder Postorder Traversals in One Traversal | C++ | Java | Stack | Binary Trees

[@takeUforward]

Please likeeee, shareeee and subscribeeeeeeee :) Also follow me at Insta: Striver_79

[@amarjeetkumar-hk2jl]

everything is right but writing Pair in" Stack st= new Stack()" giving error in intelliJ IDE.

[@imshivendra]

@@amarjeetkumar-hk2jl Where is the link of this problem? Is it not available on Leetcode.

[@greyhat6599]

Hattss off to you man !! 😄🎩

[@dopamaniac_]

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

[@prashudeshmukh7902]

If someone dosn't watch the tutorial , i don't think he will be able come up with such an approach in the interview .

[@AMANZAKIRHUSAINMODAN]

exactly

[@TusharKumar-ty8kh]

i think all these data structures took a lot of try and error and time to develop

[@mansijoshi5643]

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.

[@suar_pilla]

idhar udhar se maaal uthae ga to aise hoga

[@ThePROestRedn99]

​@@suar_pilla apne name thik rakhe ho akdm😮

[@ASHUTOSHSHARMA-us6hd]

@@suar_pilla 😂😂😂exactly to the point

[@UtkarshShrivastava6009]

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); }

[@pronoobad6611]

I was thinking about this in whole video ,, so that's why i can't get what video is all about 🥲🥲🥲🥲

[@vedansh4033]

sahi baat hai, pata nahi itna complicate kyo kiya

[@himalayagupta7744]

@@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.

[@VishalGupta-xw2rp]

Woahhhhh thanx man

[@VishalGupta-xw2rp]

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 🙋‍♂️

[@amarks444]

I found this much easier than other 3 iterative versions.

[@sanginigupta1312]

true

[@CodePinaka]

+1

[@harshitrautela6585]

same here, the intuition was very easy to grasp.

[@dogwoofwoof8154]

true lol

[@qwertykeyboard1671]

Bhai job lagi??? 2 saal hogye codeforces ki rating???

[@sarthakragwan5248]

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.

[@deepaksarvepalli2344]

This approach blews my mind....

[@averylazyandweirdhuman]

What?? This is cool man! My college could never!!!!!! Striver thanks for putting light on such solutions. You're just awesome!

[@rahular4596]

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); }

[@ganeshkamath89]

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

[@sumitkanth5349]

What is this auto mean " auto it = st.top(); " ?

[@kathanvakharia]

‘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.

[@sumitkanth5349]

@@kathanvakharia okii thanks ✌️

[@theSeniorSDE]

Striver, this was not much difficult. Understood this properly and took notes as well.

[@himansh4812]

@@gautham7244 wtf. 😂

[@tanishq2766]

Sure but, Coming up on your own is ig

[@tanya8353]

I have watched many of your lectures, but this is the first one where I couldn't understand the intuition behind the code!!

[@sweetyagrawal9746]

the return type of the function in the c++ code should be void instead of vector just a little correction

[@stith_pragya]

UNDERSTOOD...Thank You So Much for this wonderful video.....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@akhilesh59]

This was Amazing. Didn't expected a solution with this level of simplicity :) . Maza aaya!

[@shivangisrivastava1158]

Hats off to the approach, stunningly explained 😍

[@imshivendra]

Where is the link of this problem? Is it not available on Leetcode.

[@omkarraskar8664]

@@imshivendra it is on codestudio

[@lifehustlers164]

Completed 14/54(25% done) !!!

[@MrSaint-ch6xn]

I never seen an approach like this 🔥🔥🔥

[@thomasgeorge4578]

What a great approach 👏🏽👏🏽, haven't seen this anywhere

[@arpitjain6844]

This is a great video, You playlists are really helping us a lot.

[@deepakgurjar3746]

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

[@HemangSinghal-op5ep]

Badiya Advice Bhai! Same experience with me!

[@VAISHNAVIP-z6j]

It's easier than all other traversals❤️❤️💐💐

[@satyamsrivastava9083]

I don't know this approach it is amazing thanks Bro for the amazing video

[@kishorsahoo5446]

I love the content ❤.the man behind a successful coder. Salute to this man 🙏❤🎉

[@BiharCentralSchool]

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

[@cinime]

Understood! So wonderful explanation as always, thank you very much!!

[@imshivendra]

Where is the link of this problem? Is it not available on Leetcode.

[@shauryashekhar]

Just too good you are! Keep making the great content and thanks.

[@imshivendra]

Where is the link of this problem? Is it not available on Leetcode.

[@nawabkhan4916]

great work, and have lots of sponsor ad so that you can provide great videos.

[@JayPatel-sn7it]

Should we cramming this algorithm or try to understand intuition behind it???

[@nileshsinha7869]

please do like the video if u get some value out of it. This is priceless❤

[@sharmanihal99]

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

[@prabhakaran5542]

Understood ❤

[@stevefox2318]

This approach blew my whole mind to pieces ❤️‍🔥❤️‍🔥 thanks raj

[@prasaddd77]

What is the name of the leetcode problem for this? Can you provide a link for that ?

[@tps8470]

Loved the solution

[@sauravchandra10]

Maza agya, perfect last video to consolidate all the concepts of traversals.

[@saikirank6357]

Very well explained. Thank you is a small word.

[@vaalarivan_p]

1:00 - 3:25 edoc urhtlklaw: 8:55

[@curs3m4rk]

This is a really nice concept. All in one. thanks

[@ritikshandilya7075]

Thankyou so much striver

[@sankalpjain4841]

Nicely Explained..

[@nethanchowdary4657]

This video is a gem 💎

[@meetsoni1938]

Very elegantly done 👍

[@Aman-tg5lw]

op bhai bhot accha explain kia

[@anshumanyadav5546]

so basically in a pair the left part is termed as first and the second part separated by comma is called second in cpp?

[@satyampandey5584]

yes

[@krishnaradhey2814]

Looks like we have to mug up this approach , while traversing with just one STACK. AGREE OR NOT.....

[@takeUforward]

Yes you have to, it is kind of an approach you cannot derive at a spot...

[@PalakMittal]

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..

[@BiharCentralSchool]

Absolutely Correct

[@kotipallimadhumeher71]

dont you think,that makes it little complex

[@rohitsinha9391]

It was worth watching bro...Awesome approach

[@mriduljain1981]

completed lecture 13 of Tree Playlist.

[@samuelfrank1369]

Understood. Thanks a lot.

[@iamnottech8918]

best as always... thnks

[@zeal1059]

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.

[@Yash-uk8ib]

Sir, if possible, plzz make a video on morris traversals as well. Much needed

[@takeUforward]

At the last..

[@Yash-uk8ib]

@@takeUforward thank u sir

[@sigmaschoolmodasa]

Great Approach and Great Explanation!

[@ajaykushwaha6137]

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?

[@bharathkumar5870]

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)..

[@bharathkumar5870]

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)

[@ajaykushwaha6137]

@@bharathkumar5870 You got this from recursive approach right? That is also how I thought, but couldn't have been able to do it iteratively.

[@PrinceKumar-el7ob]

@@bharathkumar5870 nice intuition loved it !!

[@himalayagupta7744]

@@bharathkumar5870 Thank you so much Bharath.

[@gangsta_coder_12]

Great explanation 🔥🔥🔥🔥

[@rsachdeva1020]

Awesome approach and explanation

[@PrinceKumar-el7ob]

No need to pop multiples times just pop one time in the postorder condition only !!

[@73-sarthakpandey25]

true

[@sunnykumarpal9679]

Thank you bhaiya for making such a fabulous series

[@rohitranjan8132]

Great Explanation 🔥🔥🔥🔥

[@pramitsrivastava2579]

thanks sir

[@codding32world50]

whattt a aproachh!!!!!!!!!!!

[@pratikshadhole6694]

wanted to know if the intuition behind this code is needed to understand or if we need to mug up

[@083_h_nitishkumarjha3]

same ? did u got the intution?

[@mayanksingh5783]

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.

[@pratikshadhole6694]

@@mayanksingh5783 perfect dude. thanks

[@Learnprogramming-q7f]

Thank you Bhaiya

[@arpitpandey578]

This one is better than any other traversal.

[@sakshamjain6015]

What is the intutition behind this approach?

[@ankitmeena6842]

# 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]]

[@Nainalarenukadevi9196-dh8rz]

much useful

[@dikshasoni52a98]

What is better to use....... iterative or recursive method?

[@MrOO-ix5qr]

should we learn traversing through iteration and recursion both ?

[@nainagarg6668]

The links in the description for the problem link and cpp code link are not of this question. Please look into it.

[@takeUforward]

Okayy

[@abhishekgoswami2616]

mazzaaa hii agya bhaiaa ye dekh kar

[@Its.all.goodman]

very nice explanation bro... much appreciated

[@tridibeshmisra9426]

@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!!

[@takeUforward]

It was pre-defined, pretty tough to come up with such hacks

[@umeshkaushik710]

Great Work

[@Virtualexist]

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??

[@hakunamatata-nl4js]

Thanks

[@DeadPoolx1712]

UNDERSTOOD;

[@nitingoyal5515]

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?

[@mohit7717]

THank you so much!

[@parthsalat]

Understood!

[@studynewthings1727]

Understood.

[@utsavseth6573]

FInally, something I can remember.

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

Wowww❤

[@Ajay-ei2jo]

Thank you sir.

[@arihantjainajbil8182]

bahut pyaara

[@dikshasoni52a98]

in the website.. the question link linked is of postorder traversal and not this question

[@jainilpanchal2000]

Mind-boggling 🧐

[@vakhariyajay2224]

Thank you very much.

[@vimalvinayak001]

Till now, the question link has not been updated. Can anyone provide the question link of any website?

[@adityapandey23]

Understood

[@shineinusa]

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; }

[@shivam4you744]

completed bhaiya : )

[@AnkitKumar-jm3cz]

best appproach bhaiya

[@technicaldoubts5227]

totally understood thankyouuu so much !!

[@as_a_tester]

tysm striver bhai

[@funenjoynilaypatel4553]

#include using namespace std; #define int int64_t struct node{ int data; struct node* left; struct node* right; node(int val){ data = val; left = NULL; right = NULL; } }; vector preOrder, inOrder, postOrder; void singleTraversal(node* curr){ if(curr == NULL) return; stack st; st.push({curr, 1}); while(!st.empty()){ pair p = st.top(); st.pop(); if(p.second == 1){ preOrder.push_back(p.first -> data); st.push({p.first, p.second + 1}); if(p.first -> left != NULL){ st.push({p.first -> left, 1}); } }else if(p.second == 2){ inOrder.push_back(p.first -> data); st.push({p.first, p.second + 1}); if(p.first -> right != NULL){ st.push({p.first -> right, 1}); } }else if(p.second == 3){ postOrder.push_back(p.first -> data); } } return; } signed main(){ /* Code by :- Nilay Patel (nilay__patel) */ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); struct node* root = new node(1); root -> left = new node(2); root -> right = new node(3); root -> left -> left = new node(4); root -> left -> right = new node(5); root -> left -> right -> left = new node(8); root -> right -> left = new node(6); root -> right -> right = new node(7); root -> right -> right -> left = new node(9); root -> right -> right -> right = new node(10); singleTraversal(root); cout

[@deveshdubey6776]

OP bhaiya🔥🔥 maza aa gaya:)

[@rupalikumari8829]

Understood : )

[@nagavedareddy5891]

Huge respect...❤👏

[@SatyamKumar-bw4vi]

Hare krishna!