• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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.

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




Must Read Chapters:



The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave