🙏

জয়  শ্রী  রাম

🕉

---

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:



Login to Access Content

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: