Iterative Postorder traversal of binary tree using one stack

[@santhosh087]

I almost got the logic while thinking of the problem. I couldn't think of that inner while loop to break the loop when we are done with all the lefts. Though I could understand your initial explanation, its little tough to match the same with the code. Thanks for the great explanation!!.

[@uditgaba1450]

Thanks for the explanation! You are saving a lot of time for me. Instead of reading articles or reading codes sometimes , i can simply watch your video . I implemented the code on my own after this video . Code (Java):- public static void postOrderUsingSingleStack(TreeNode root) { Stack s = new Stack(); TreeNode curr = root; while(curr != null || !s.isEmpty()) { while(curr != null) { s.push(curr); curr = curr.left; } if(!s.isEmpty()) { //check is stack top has right child if(s.peek().right != null) { curr = s.peek().right; } else { TreeNode temp = s.pop(); System.out.print(temp.data+" "); while(s.size() > 0 && s.peek().right == temp) { temp = s.pop(); System.out.print(temp.data+" "); } } } }

[@kiratsaluja3522]

almost got the logic and was stuck at how to check if right is already visited or not. This explains it bang on. Thank u

[@meghnasrivastava568]

Best explanation,I have watched so far!

[@sureshiva4605]

straigh forward way ....nice....instead of using previous variable or skip counts....this looks clean

[@vvwu7194]

Thank you, better than the other explanations I have watched or read.

[@sameer_sah]

Great walkthrough. Only thing I want to point out is offer and poll are methods of queue API. We should be using push and pop of stack API.

[@mingxiao1939]

Clear and intuitive explanation! Thank you Tushar.

[@U2011-n7w]

nice explanation

[@ghostpieces2362]

Tushar, this was an amazing visual walkthrough followed by a brilliant code walkthrough. Thanks for taking the time to share :)

[@abhinav4279_]

This iterative traversal has been messing up my mind for long, not anymore.👍

[@yelururao1]

super explanation..thanks for it..please do more videos on BST , AVL and red-black tree

[@abhay7130]

bolne ke style sun ke gariyane ka hi man karta hai iske. baki sb badiya hai

[@shreyasingh-sn4bs]

Thank you for making learning so much easier :)

[@saisusritha]

Great Explanation

[@MithleshKumar-iz1dz]

You are saviour Tushar. Thanks alot!

[@student_03]

thanks a lot sir amazing explanation

[@shivamdixit8796]

exceptional explanation.... The algo explanation was so good, that i could code it just by looking halfway through the explanation.....hats off to the amazing work :)

[@JangBahadur3028]

Awsome tutorial. well explained. Helped me a lot . Thank you Tushar.

[@chenboxie6623]

Thank you Tushar, very clear. Understand better now.

[@MrRanjeetaize]

Nice explanation.. too much helping

[@adhishmalviya2408]

this guy reminds me of song..**ek tu hi yaar mera mujhe kya duniya se lena**

[@mahee96]

The only thing I was missing, was how to preserve the root which is usually popped off when doing in-order/pre-order iterative traversals, but the important note here is that, we don't pop off the root unless we see that curr.right is null and curr node is right child(KEY POINT) of latest(last) stack entry which means last entry is root, hence know we are done and pop off this right child backtrack to root. So until then root is preserved!! class stack(list): def push(self, val): self.append(val) def peek(self): return self[-1] def LRN(root): st = stack() while root or st: while root: st.push(root) root = root.left root = st.peek().right if root: continue # pop off backstack - backtracking # left node pop off x = st.pop() print(x.val, end=", ") # right, root node pop off while(st and st.peek().right == x): x = st.pop() print(x.val, end=", ") print()

[@mprasanth18]

Thanks a lot. This is very helpfull.

[@SonGoku-ep4wj]

dude you're a legend . thank you !

[@paraskamboj1039]

Thankyou so much sir

[@mnchester]

great vid

[@veronicadey6731]

So tough 🤯🤯🤯

[@falakk22]

Superb Explanation Thanks!

[@TwinbeeUK]

Possibly the clearest iterative postorder traversal of trees shown on KZbin! Will this technique of using one stack work if there are 3 or more child nodes for each parent, or would a two-stack solution be needed then?

[@DharminMajmudar]

Great explanation!

[@utkarshdwivedi586]

A quick question :: you used or in the while condition instead of using and so, whenever the curr will be null the loop will break , without giving the correct output. This thing kind of contradicts with your algorithm.

[@VishalSharma-hq5ti]

Amazing!!

[@devendradahale546]

Great 🙏

[@musheerahmed5815]

Brilliant. Thanks!!

[@saksham9170]

Rote memorization at it's peak

[@charan_75]

They are standard algorithms. How else would you explain genius?

[@jbs2491]

Thank you this was very helpful. Given that space and time complexity are the same using a single stack vs two stacks (please, correct me if I'm wrong), are there any advantages/disadvantages for using a single stack vs two stacks?

[@SunnyKumar-wp6wp]

awsm.... bro

[@adityakrishna11]

This just feels like a walkthrough. You know what's happening and how is it happening but you really don't know the why of it? I came up with this implementation which I feel like is closest to what you've explained. void recursivePostOrderTraversal(BinaryTreeNode *root) { if (root) { recursivePostOrderTraversal(root->left); recursivePostOrderTraversal(root->right); cout data left; } else { BinaryTreeNode *current = content.top(); if (current->right != NULL) { root = current->right; } else { content.pop(); cout data right) { current = content.top(); content.pop(); cout data right) { if (content.top()->right != NULL) root = content.top()->right; } } } } while (content.empty() == false); }

[@akhileshkumar-xk7so]

great work

[@vinayak186f3]

20 baar padhke bhool chuka hu , ek baar aur sahi 🙂

[@KeshariPiyush24]

hota hai mere saath bhi hota hai.....kya kar sakte haiXD

[@karthickm9846]

Great Video Tushar. In your code, you used, Stack stack = new LinkedList().. Is this correct?

[@vinutd210]

Good catch. I believe it is a typo. it should be Stack stack = new Stack();

[@vinutd210]

Tushar has used Deque in most of his code that he has referenced in the description. Hence, there are things like, "offer", "poll" in his code on the whiteboard. Here is a proper stack version of this function. public static void postOrderItrOneStack(TreeNode root){ TreeNode current = root; Stack stack = new Stack(); while(current != null || !stack.isEmpty()){ if(current != null){ stack.push(current); current = current.left; }else{ TreeNode temp = stack.peek().right; if (temp == null) { temp = stack.pop(); System.out.print(temp.val + " "); while (!stack.isEmpty() && temp == stack.peek().right) { temp = stack.pop(); System.out.print(temp.val + " "); } } else { current = temp; } } } }

[@ramakrishnaloka7946]

Is code handling the scenario of checking last popped element is equal to temp.right ???????

[@sknayak3246]

I believe, it won't work if both left and right child have same values. Kindly LMK if I am missing something here.

[@shnerdz]

we compare referenced to node, not the values of the nodes, otherwise youd be correct

[@ragingpahadi]

Simple and easy to understand ! public List postorderTraversal(TreeNode root) { List res = new ArrayList(); Stack stack = new Stack(); TreeNode lastNodeVisited = null; TreeNode curr = root; while(!stack.isEmpty() || curr != null) { if(curr != null) { stack.push(curr); curr = curr.left; } else { TreeNode x = stack.peek(); if(x.right != null && x.right != lastNodeVisited) { curr = x.right; } else { res.add(x.val); stack.pop(); lastNodeVisited = x; } } } return res; }

[@prakashkrishna2566]

whatis the use of the variable lastNodeVisited?

[@karanb2067]

explanation is great but algorithm implementation is a real head scratcher....you gotta mug it up for the most part.

[@AshishRanjan-ju7zk]

very nice...

[@nking99t]

Can you do it without addFirst() or reverse()? otherwise which would just be another preorder traversal.

[@Chandyshot]

Thanks Man

[@sanketkalokhe7400]

why we need to check if the popped node is right or not I couldn't understand that part if anyone knows the solution please let me know

[@sukritkapil2562]

thanks!!

[@thanhsonhoang8982]

thanks

[@ashok845]

Nice

[@avranj]

Where is this youtuber now?

[@987abhinav]

A little better solution (C#) internal void PostOrderTraversalUsingStack(Node cur) { Node temp = null; Stack s = new Stack(); while (cur != null || s.Count != 0) { if (cur != null) { s.Push(cur); cur = cur.left; } else { Node element = s.Peek(); if (element.right != null && element.right != temp) { cur = element.right; } else { temp = s.Pop(); Console.WriteLine(temp.data + ","); } } } }

[@waqasmalik6162]

Aray bhai mouu say supari nikal kay bol xD

[@bighneshsabat5374]

nice..

[@raghuram463]

Does Non-recursive algorithm and Iterative algorithm mean the same for Post order traversal of Binary tree?

[@vinutd210]

Yes. Iterative is a non-recursive algorithm, as we do not use a recursive call of our function here. Instead, we use our own stack to trace the tree. hope it helps.

[@helentauro3850]

It should go from right na? Which means 1,3,7.....

[@xf99]

Postorder means check left node then right node then current. If you do a recursive postorder traversal you will end up with the order shown.

[@kprabhudev]

Thanks Tushar. Maybe, this could add to simplification too: void MyTree::postOrderTravIterative() { treeNode* p = this->root; stack st; while(p != nullptr || !st.empty()) { if(p != nullptr) { st.push(p); p = p->left; } else { treeNode* node = st.top()->right; if(node == nullptr) { do{ node = st.top(); cout data right); } else { p = node; } } } }

[@veronicadey6731]

This is not an intuitive approach though if one has not practised enough

[@ziminfan1664]

This is the most intuitive approach actually. It obeys the same way stack works in the recursive case.

[@anshusharma1983]

The code becomes very simple if you can keep the track of visited nodes. Here is my version - public static void printPostOrderUsingStackAndVisited(Node root) { Stack stack = new Stack(); Set visited = new HashSet(); stack.push(root); while (!stack.isEmpty()) { Node current = stack.peek(); if (current.left != null && !visited.contains(current.left)) { stack.push(current.left); } else if (current.right != null && !visited.contains(current.right)) { stack.push(current.right); } else { visited.add(current); System.out.println(stack.pop().value); } } }

[@davegould4940]

extra space

[@TwinbeeUK]

@@davegould4940 I would think the `contains()` operation will dramatically slow things down too if performance is a concern.

[@sindhuprasad6964]

Does this algorithm work if there are duplicates in the tree?

[@prashidell8980]

It will go into infinite loop in case of duplicate.

[@vinutd210]

@@prashidell8980 I am not sure if this is correct. When he compares to see if the popped node was the right of the root, he compares the object, and not just the value. Hence, it is not a duplicate. you pass an input of all nodes with same value, and it still will print the traversal. Please correct me if I am wrong.

[@alexcomas2934]

Since you are comparing objects, you compare references (memory addresses) so your nodes will always be different even if they are identical.

[@aman0509]

Thanks for simplifying the things. Have 1 question though, for line "while(!stack is empty() && temp == stack.peek().right)", why did you use while loop instead we can use 'if' statement for condition check? I am confused here.

[@dharanyuvi6951]

"if" doesn't work bro Because imagine if you have a bit complicated tree with right node nested 3 times So, at that time think u traversed till the bottom right corner -> here u printed left and right nodes of the last bottom right family already -> now u have to jump back to pop and print the parent -> grandparent to finish the postOrder so "while" is the best fit -> especially temp == stack.peek.right plays a huge role. paper workout and debug to get more clear thoughts Thanks for asking

[@wasp4932]

why peek,not peak?

[@xf99]

peek (at) means to take a look at something (or read, non-destructively); peak means the summit of a mountain, e.g.

[@abhishekanand3706]

2 is not twthooooo :))

[@Tenacioustarantula]

Sounds a little complex and the explanation doesn't make it any easier ,can be better

[@vishaltanawade7637]

Why are u talking in British English ,... Speak in Normal English .. you are from India not from London 😂😂😂😂

[@dc6940]

Its his choice, who are you to decide. If you dont like, dont watch the channel. He is helping people

[@vishaltanawade7637]

@@dc6940 Sorry *Shaktimaan* 😂😂😝

[@jamesqiu6715]

Not your best work. Such a hurry from the begin to end ...

[@yangwang24]

It seems like the postorder using traversal is difficult than preorder and inorder.

[@lsdxsaurabh2798]

when you are a drunk and try to speak in english....

[@niketandoddamani1093]

Great Explanation