L7. Postorder Traversal of Binary Tree | C++ | Java | Code Explanation

Postorder traversal is a fundamental depth-first search (DFS) strategy used in binary trees where the processing of nodes follows a strict Left-Right-Root sequence. This comprehensive study guide explores the mental model, recursive execution flow, and complete code implementations in both C++ and Java.

1. Why Do We Need Tree Traversals?

Unlike linear data structures such as arrays, linked lists, stacks, and queues—which have a single logical path from start to finish—hierarchical data structures like trees branch out in multiple directions.

• The Problem: To inspect, search, or process every node in a tree, we need a standardized, systematic strategy.
• The Solution: Traversals dictate the exact visiting order. Postorder Traversal is uniquely suited for scenarios where a parent node's operation depends entirely on the results of its children (such as evaluating mathematical expressions, bottom-up tree destruction, or calculating subtree sizes/heights).

2. Core Mental Model: The Postorder Rule

The acronym for Postorder Traversal is LRR (Left-Right-Root) or simply Left, Right, Root.

• Left: Recursively traverse the left subtree first.
• Right: Recursively traverse the right subtree second.
• Root: Process (print or evaluate) the current root node last (hence post-order).

Real-Life Analogy: Cleaning or Deleting a Folder Structure

Think of a computer directory containing folders and subfolders. If you want to delete a parent folder containing files and subfolders, you cannot delete the parent folder first because the operating system blocks it while it contains items.

• You must first go inside and delete everything on the Left (sub-folders).
• Then go to the Right (remaining contents).
• Only after both left and right contents are completely wiped can you delete the root folder itself. That bottom-up cleanup mirrors Postorder Traversal.

3. Step-by-Step Recursive Strategy

The implementation relies entirely on the call stack via recursion. We maintain three simple rules:

1. Base Condition: If the current node is null (or points to nullptr in C++), return immediately.
2. Recursive Left Call: Call the traversal function on node.left.
3. Recursive Right Call: Call the traversal function on node.right.
4. Process Root: Print or store the current node's data after both recursive calls complete.

4. Visualizing the Recursive Flow on a Sample Tree

Let's trace the postorder traversal step-by-step on a sample binary tree.

          1
        /   \
       2     3
      / \   / \
     4   5 7   8
        /     / \
       6     9  10

Detailed Trace Walkthrough:

1. Start at Root (1):
   • Go to Left (2).
2. At Node (2):
   • Go to Left (4).
3. At Node (4):
   • Go to Left (null) -> returns.
   • Go to Right (null) -> returns.
   • Left and Right are done -> Print 4. Return to parent (2).
4. Back at Node (2):
   • Left child (4) is done. Now go to Right (5).
5. At Node (5):
   • Go to Left (6).
6. At Node (6):
   • Go to Left (null) -> returns.
   • Go to Right (null) -> returns.
   • Left and Right are done -> Print 6. Return to parent (5).
7. Back at Node (5):
   • Left child (6) is done. Go to Right (null) -> returns.
   • Left and Right are done -> Print 5. Return to parent (2).
8. Back at Node (2):
   • Left (4) and Right (5) are both done -> Print 2. Return to parent (1).
9. Back at Root (1):
   • Left subtree (2) is done. Now go to Right subtree (3).
10. At Node (3):
    • Go to Left (7).
    • [Traverses and prints 7, then processes right branch 8 (which visits 9, prints 9, visits 10, prints 10, prints 8), then prints 3]
11. Back at Root (1):
    • Left and Right subtrees are completely finished -> Print 1.

Final Postorder Output Sequence: 4 -> 6 -> 5 -> 2 -> 7 -> 9 -> 10 -> 8 -> 3 -> 1

5. Code Implementation: C++

Below is the clean, production-ready C++ recursive implementation for postorder traversal.

#include <iostream>
#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    void postorderHelper(TreeNode* root, vector<int>& result) {
        // Base case: if node is null, return
        if (root == nullptr) {
            return;
        }
        
        // 1. Traverse Left Subtree
        postorderHelper(root->left, result);
        
        // 2. Traverse Right Subtree
        postorderHelper(root->right, result);
        
        // 3. Process Root Node
        result.push_back(root->val);
    }

public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        postorderHelper(root, result);
        return result;
    }
};

6. Code Implementation: Java

Below is the equivalent clean, robust Java recursive implementation.

import java.util.ArrayList;
import java.util.List;

// Definition for a binary tree node.
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 {
    private void postorderHelper(TreeNode root, List<int> result) {
        // Base case: if node is null, return
        if (root == null) {
            return;
        }
        
        // 1. Traverse Left Subtree
        postorderHelper(root.left, result);
        
        // 2. Traverse Right Subtree
        postorderHelper(root.right, result);
        
        // 3. Process Root Node
        result.add(root.val);
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Definition: Postorder traversal follows the Left-Right-Root (LRR) visiting sequence.
• Root Position: The root node is always processed last, after both its left and right subtrees have been completely explored.
• Base Case: Always check for null (or nullptr) at the beginning of your recursive function to terminate traversal safely.
• Call Stack Management: Recursion implicitly utilizes the system call stack to remember parent states during backtracking.
• Practical Use Cases: Ideal for bottom-up operations such as deleting trees, parsing postfix expressions, or computing directory sizes on disk.
• Simplicity: Do not overcomplicate tree problems; break them down into self-contained recursive steps (Left, Right, Action).