1. What is Postorder Traversal?

Postorder traversal is a type of depth-first traversal in binary trees. It follows this order:

Left Subtree → Right Subtree → Root Node

This means the node is visited after both its children are completely processed — hence the name post-order.

2. Where is Postorder Traversal Used?

Postorder traversal is used when:

• You need to delete a binary tree safely.
• You are evaluating arithmetic expressions stored in a binary tree.
• You want to free memory in bottom-up order.
• In applications like syntax trees, expression trees, compilers, etc.

3. Conceptual Example

Consider the binary tree below:

        1
       / \
      2   3
     / \
    4   5

Postorder Traversal Order:

Left → Right → Root

=> 4 → 5 → 2 → 3 → 1

4. Pseudocode

function postorder(node):
    if node is null:
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)

5. Java Implementation

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.val = value;
        this.left = null;
        this.right = null;
    }
}

public class PostorderTraversal {

    public void postorder(TreeNode node) {
        if (node == null) {
            return;
        }

        // Step 1: Traverse left
        postorder(node.left);

        // Step 2: Traverse right
        postorder(node.right);

        // Step 3: Visit node
        System.out.print(node.val + " ");
    }

    public static void main(String[] args) {
        // Build the tree:
        //         1
        //        / \
        //       2   3
        //      / \
        //     4   5

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        PostorderTraversal tree = new PostorderTraversal();
        System.out.println("Postorder Traversal:");
        tree.postorder(root);  // Output: 4 5 2 3 1
    }
}

6. Visual Flow Diagram (Text-Based)

        1
       / \
      2   3
     / \
    4   5

Postorder:
- Visit 4 (left of 2)
- Visit 5 (right of 2)
- Visit 2 (root of subtree)
- Visit 3 (right of 1)
- Visit 1 (root)

7. Time and Space Complexity

Time Complexity:

• Each node is visited exactly once → O(n)
  where n is the number of nodes.

Space Complexity:

• O(h) for the recursion stack (h = height of the tree)
  • Balanced Tree: O(log n)
  • Skewed Tree: O(n)