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!!.
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+" "); } } } }
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 :)
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 RU-vid! 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?
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; } } } }
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 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); }
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()
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
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.
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); } } }
