Binary TreesProblem 8 of 35

Postorder Traversal of a tree both using recursion and Iteration

Brute Force
Time: O(n)
Space: O(n)
Optimal
Time: O(n)
Space: O(n)

Problem Statement

Given a binary tree, perform postorder traversal (Left -> Right -> Root) and return the list of node values. Implement both recursive and iterative approaches.

Example:

1 / \ 2 3 / \ 4 5
  • Input: Root of the above tree
  • Output: [4, 5, 2, 3, 1]

Approach 1: Recursive (Simple DFS)

Intuition

Follow the postorder pattern: traverse left subtree, traverse right subtree, then visit root.

Algorithm

  1. Recursively traverse left subtree
  2. Recursively traverse right subtree
  3. Process/visit the current node
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public void postorderRecursive(TreeNode root, List<Integer> result) {
        if (root == null) return;
        
        postorderRecursive(root.left, result);   // Left
        postorderRecursive(root.right, result);  // Right
        result.add(root.val);                     // Root
    }
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderRecursive(root, result);
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Visit each node once
  • Space Complexity: O(n) - Recursion stack for skewed tree

Approach 2: Iterative (Using Two Stacks)

Intuition

Use two stacks. First stack helps traverse in Root -> Right -> Left order. Second stack collects and reverses to get Left -> Right -> Root.

Algorithm

  1. Push root to first stack
  2. Pop from first stack, push to second stack
  3. Push left child, then right child to first stack
  4. Pop all from second stack to get result
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> postorderTwoStacks(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        
        while (!stack1.isEmpty()) {
            TreeNode node = stack1.pop();
            stack2.push(node);
            
            if (node.left != null) stack1.push(node.left);
            if (node.right != null) stack1.push(node.right);
        }
        
        while (!stack2.isEmpty()) {
            result.add(stack2.pop().val);
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Visit each node once
  • Space Complexity: O(n) - Two stacks together hold all nodes

Approach 3: Iterative (Using One Stack)

Intuition

Use one stack with careful tracking. Process a node only after both children are processed. Track the last processed node to determine direction.

Algorithm

  1. Use a pointer to track last visited node
  2. If coming from parent, go left if possible, else go right, else process
  3. If coming from left child, go right if possible, else process
  4. If coming from right child, process and go up
java
import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> postorderOneStack(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        TreeNode lastVisited = null;
        
        while (current != null || !stack.isEmpty()) {
            // Go to the leftmost node
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            
            TreeNode peekNode = stack.peek();
            
            // If right child exists and not processed yet
            if (peekNode.right != null && lastVisited != peekNode.right) {
                current = peekNode.right;
            } else {
                // Process the node
                result.add(peekNode.val);
                lastVisited = peekNode;
                stack.pop();
            }
        }
        
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Visit each node once
  • Space Complexity: O(n) - Stack holds nodes along the path

Approach 4: Reverse of Modified Preorder

Intuition

Postorder (L-R-Root) is reverse of modified preorder (Root-R-L). Do Root-R-L traversal and reverse the result.

Key Takeaways

  1. Postorder = Left -> Right -> Root (process root last)
  2. Two-stack approach is easier to understand and implement
  3. One-stack approach requires tracking the last visited node
  4. Postorder is useful for deleting tree, evaluating postfix expressions
  5. Postorder iterative is more complex than preorder/inorder iterative
Previous
Preorder Traversal of a tree both using recursion and Iteration
Next
Left View of a tree