Complexity Analysis of Brute Force

• Time Complexity: $O(N^2)$. In a skewed tree (e.g., a linked list structure), concatenating arrays or lists at every step involves copying elements repeatedly. If a node at depth $k$ returns a list of size $k$, and its parent copies that list, the total operations become proportional to the sum of $1$ to $N$, which is quadratic.
• Space Complexity: $O(N^2)$ in the worst case due to the creation of multiple temporary list objects during concatenation.

Why It Fails

While this approach is logically correct, it is inefficient for large trees. The excessive memory allocation and data copying can lead to poor performance or Memory Limit Exceeded (MLE) errors in strict environments, and it fails to demonstrate the optimal $O(N)$ manipulation required in technical interviews.

Core Insight for Binary Tree Postorder Traversal

The key intuition for an optimal LeetCode 145 Solution is to use a single mutable data structure (like a dynamic array or vector) that is passed by reference (or available globally) throughout the recursion.

Instead of creating and returning new lists at each node, we maintain one result list. We traverse the tree using the standard recursive stack. The crucial invariant of Postorder Traversal is that a node is never added to the result list until both its left and right subtrees have fully completed their execution.

Visual Description: Imagine the recursion tree. The algorithm plunges deep down the left side of the tree first. Nothing is written to the result list during this descent. It is only when the recursion hits a null leaf and returns (pops from the stack) that the algorithm considers adding a value. Even then, it checks the right child. Only after the function calls for the left and right children return does the current node "commit" its value to the list. This ensures the "bottom-up" processing characteristic of Postorder traversal.

Algorithm Strategy: Tree DFS - Recursive Postorder Traversal

To implement the optimal solution for interviews, we utilize a helper function (or a private method) to handle the recursion.

1. State Maintenance: We maintain a single collection (List/Vector) result to store the traversal sequence.
2. Recursive Function: We define a traverse function that takes a node and the result structure.
3. Base Case: If the current node is null, we return immediately. This stops the recursion at leaf nodes.
4. Recursive Steps:
   • First, call traverse on node.left. This ensures all nodes in the left subtree are processed and added to result before the current node.
   • Second, call traverse on node.right. This ensures all nodes in the right subtree are processed and added to result before the current node.
5. Processing Step: After both recursive calls return, append node.val to result.

This strategy guarantees that for any node $P$, all nodes in its subtrees appear earlier in the result list than $P$ itself.

Execution Flow

1. Initialization: Create an empty list result.
2. Start Recursion: Call the helper function dfs(root, result).
3. Step-by-Step Recursion (at any given node):
   • Check: Is node null? If yes, return to caller.
   • Go Left: The function calls itself for node.left. The program stack grows. This continues until a leaf's left child (null) is reached.
   • Go Right: After returning from the left, the function calls itself for node.right.
   • Visit: Once control returns from both children, the algorithm executes result.add(node.val).
   • Return: The function finishes for node and pops off the stack, returning control to node's parent.
4. Completion: When the initial call dfs(root) returns, result contains the complete postorder traversal.

Proof of Correctness

The correctness follows directly from the inductive definition of Postorder Traversal.

• Base Case: For a null tree, the algorithm does nothing, returning an empty list. This is correct.
• Inductive Step: Assume the algorithm correctly generates the postorder sequence for trees of height $< h$. For a tree of height $h$ rooted at $R$, the algorithm first executes on $R_{left}$ (height $< h$) and then on $R_{right}$ (height $< h$). By the hypothesis, these generate the correct sequences $S_{left}$ and $S_{right}$. The algorithm then appends $R$. The final sequence is $S_{left} \oplus S_{right} \oplus \{R\}$, which is exactly the definition of postorder traversal.

Reference Implementation

C++ Solution for LeetCode 145

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        traverse(root, result);
        return result;
    }

private:
    // Helper function implementing the Recursive Postorder pattern
    void traverse(TreeNode* node, vector<int>& result) {
        if (node == nullptr) {
            return;
        }
        
        // Pattern: Left -> Right -> Root
        traverse(node->left, result);
        traverse(node->right, result);
        result.push_back(node->val);
    }
};

Java Solution for LeetCode 145

java
/**
 * Definition for a binary tree node.
 * 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> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }
    
    // Helper method strictly following the DFS Postorder logic
    private void traverse(TreeNode node, List<Integer> result) {
        if (node == null) {
            return;
        }
        
        // Visit Left Subtree
        traverse(node.left, result);
        
        // Visit Right Subtree
        traverse(node.right, result);
        
        // Visit Root Node
        result.add(node.val);
    }
}

Python Solution for LeetCode 145

python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        
        def traverse(node):
            if not node:
                return
            
            # Pattern: Recursive Postorder (Left, Right, Root)
            traverse(node.left)
            traverse(node.right)
            result.append(node.val)
        
        traverse(root)
        return result

• Mistake: Using functional-style list concatenation inside the recursion.
• Correction: Pass a single mutable list reference to the helper function to maintain $O(N)$ time complexity.