Iterative Postorder Traversal

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io
Postorder Traversal:
In Preorder Traversal we visit / process the parent first and then the child nodes. It is exactly opposite in Postorder Traversal. In Postorder traversal we first visit / process the childNodes and then process the parent. So if we do similar to what we did in Iterative Preorder Traversal then we would actually get the nodes in the exact opposite order of the postorder. To achieve this we would have to push the leftChild first followed by rightChild, which was opposite in iterative Preorder traversal. Take a simple example and it would become clear.Preorder of following tree is 1 > 2 > 3 .
1 / \ 2 3
Postorder of the above tree would be 2 > 3 > 1.
Look how if we convert the Preorder traversal to be 1 > 3 > 2 then the Postorder becomes exact reverse order of the Preorder. This is achieved by pushing rightChild (in our case 3) and then leftChild (in our case 2).
The above approach would definitely work for us. We will just have to keep in mind that we are getting nodes in the reverse order of the postorder.
Java code:
/**
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> output = new ArrayList<>();
if (root == null) {
return output;
}
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while(!stack.isEmpty()) {
//visit
TreeNode currNode = stack.pop();
//process
output.add(currNode.val);
if (currNode.left != null) {
stack.push(currNode.left);
}
if (currNode.right != null) {
stack.push(currNode.right);
}
}
Collections.reverse(output); // this is important, since the order in which
// we have gotten the nodes is the exact opposite order of the Postorder
return output;
}
}
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Must Read Chapters:
 Iterative Preorder Traversal

Iterative Postorder Traversal
w/ Single Stack 
Powerful Approach of
Iterative Inorder Traversal  How to track traversed paths in DFS
Instructor:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn