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!!.
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); }
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+" "); } }
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; } } } }
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.
Possibly the clearest iterative postorder traversal of trees shown on RUclips! 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?
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?
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()
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); } } }
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.
@@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.
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 :)
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.
"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
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!!.
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);
}
very nice...
thanks!!
super explanation..thanks for it..please do more videos on BST , AVL and red-black tree
Aray bhai mouu say supari nikal kay bol xD
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+" ");
}
}
}
}
This iterative traversal has been messing up my mind for long, not anymore.👍
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 + ",");
}
}
}
}
Thank you for making learning so much easier :)
Great Video Tushar. In your code, you used, Stack stack = new LinkedList().. Is this correct?
Good catch. I believe it is a typo. it should be Stack stack = new Stack();
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;
}
}
}
}
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.
nice explanation
explanation is great but algorithm implementation is a real head scratcher....you gotta mug it up for the most part.
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
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.
So tough 🤯🤯🤯
Can you do it without addFirst() or reverse()? otherwise which would just be another preorder traversal.
Tushar, this was an amazing visual walkthrough followed by a brilliant code walkthrough. Thanks for taking the time to share :)
Thank you, better than the other explanations I have watched or read.
I believe, it won't work if both left and right child have same values. Kindly LMK if I am missing something here.
we compare referenced to node, not the values of the nodes, otherwise youd be correct
Best explanation,I have watched so far!
Awsome tutorial. well explained. Helped me a lot . Thank you Tushar.
Nice explanation.. too much helping
straigh forward way ....nice....instead of using previous variable or skip counts....this looks clean
Thanks a lot. This is very helpfull.
Rote memorization at it's peak
They are standard algorithms. How else would you explain genius?
thanks a lot sir
amazing explanation
Thankyou so much sir
Is code handling the scenario of checking last popped element is equal to temp.right ???????
Possibly the clearest iterative postorder traversal of trees shown on RUclips! 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?
Where is this youtuber now?
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?
This is not an intuitive approach though if one has not practised enough
This is the most intuitive approach actually. It obeys the same way stack works in the recursive case.
Great Explanation
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()
Great Explanation
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
dude you're a legend . thank you !
bolne ke style sun ke gariyane ka hi man karta hai iske. baki sb badiya hai
Clear and intuitive explanation! Thank you Tushar.
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;
}
whatis the use of the variable lastNodeVisited?
awsm.... bro
Brilliant. Thanks!!
great vid
this guy reminds me of song..**ek tu hi yaar mera mujhe kya duniya se lena**
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);
}
}
}
extra space
@@davegould4940 I would think the `contains()` operation will dramatically slow things down too if performance is a concern.
Does Non-recursive algorithm and Iterative algorithm mean the same for Post order traversal of Binary tree?
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.
Thank you Tushar, very clear. Understand better now.
You are saviour Tushar. Thanks alot!
Superb Explanation Thanks!
Great 🙏
thanks
It should go from right na?
Which means 1,3,7.....
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.
20 baar padhke bhool chuka hu , ek baar aur sahi 🙂
hota hai mere saath bhi hota hai.....kya kar sakte haiXD
Amazing!!
Thanks Man
Great explanation!
2 is not twthooooo :))
Does this algorithm work if there are duplicates in the tree?
It will go into infinite loop in case of duplicate.
@@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.
Since you are comparing objects, you compare references (memory addresses) so your nodes will always be different even if they are identical.
nice..
Nice
great work
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 :)
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;
}
}
}
}
Why are u talking in British English ,... Speak in Normal English .. you are from India not from London 😂😂😂😂
Its his choice, who are you to decide. If you dont like, dont watch the channel. He is helping people
@@dc6940 Sorry *Shaktimaan* 😂😂😝
Sounds a little complex and the explanation doesn't make it any easier ,can be better
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.
"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
when you are a drunk and try to speak in english....
why peek,not peak?
peek (at) means to take a look at something (or read, non-destructively); peak means the summit of a mountain, e.g.
Not your best work. Such a hurry from the begin to end ...
It seems like the postorder using traversal is difficult than preorder and inorder.