Binary Tree Postorder Traversal

LeetCode 145: Binary Tree Postorder Traversal Solution & Explanation

Problem Overview

TL;DR: The optimal solution recursively visits the left child, then the right child, and finally processes the current node, accumulating values into a single result list.

The LeetCode 145 problem, Binary Tree Postorder Traversal, asks us to traverse a binary tree and return a list of its node values in a specific order. In a postorder traversal, we must process the subtrees of a node before processing the node itself. Specifically, for every node, the traversal order is:

1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit (record) the root node.

This is a fundamental tree operation and a popular interview question used to test understanding of Depth-First Search (DFS) and recursion.

Brute Force Approach for Binary Tree Postorder Traversal

A naive approach to solving the Binary Tree Postorder Traversal problem often stems from a direct translation of the mathematical definition into code using functional list concatenation.

In this approach, a developer might implement a function that returns a new list for every node. The logic typically looks like this: postorder(node) = postorder(node.left) + postorder(node.right) + [node.val]

Naive Pseudo-Code

function postorder(node):
    if node is null:
        return empty list
    
    left_list = postorder(node.left)
    right_list = postorder(node.right)
    
    // Concatenate lists
    return concatenate(left_list, right_list, [node.val])

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.

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.

Pattern Reuse Notes

The Tree DFS - Recursive Postorder Traversal pattern is a foundational building block for many advanced tree problems.

• LeetCode 104: Maximum Depth of Binary Tree: Uses postorder logic implicitly; you calculate the depth of left and right children before determining the depth of the current node.
• LeetCode 110: Balanced Binary Tree: Requires checking the height balance of children (bottom-up) before validating the current node.
• LeetCode 124: Binary Tree Maximum Path Sum: Calculates the max path sum from children subtrees before computing the max path through the current root.
• LeetCode 337: House Robber III: Decisions to rob or not rob a node depend entirely on the optimal results returned from its children (Postorder processing).

Reference Implementation

C++ Solution for LeetCode 145

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    vector<int> postorderTraversal(TreeNode* root) {
15        vector<int> result;
16        traverse(root, result);
17        return result;
18    }
19
20private:
21    // Helper function implementing the Recursive Postorder pattern
22    void traverse(TreeNode* node, vector<int>& result) {
23        if (node == nullptr) {
24            return;
25        }
26        
27        // Pattern: Left -> Right -> Root
28        traverse(node->left, result);
29        traverse(node->right, result);
30        result.push_back(node->val);
31    }
32};

Java Solution for LeetCode 145

1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    public List<Integer> postorderTraversal(TreeNode root) {
18        List<Integer> result = new ArrayList<>();
19        traverse(root, result);
20        return result;
21    }
22    
23    // Helper method strictly following the DFS Postorder logic
24    private void traverse(TreeNode node, List<Integer> result) {
25        if (node == null) {
26            return;
27        }
28        
29        // Visit Left Subtree
30        traverse(node.left, result);
31        
32        // Visit Right Subtree
33        traverse(node.right, result);
34        
35        // Visit Root Node
36        result.add(node.val);
37    }
38}

Python Solution for LeetCode 145

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7
8class Solution:
9    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
10        result = []
11        
12        def traverse(node):
13            if not node:
14                return
15            
16            # Pattern: Recursive Postorder (Left, Right, Root)
17            traverse(node.left)
18            traverse(node.right)
19            result.append(node.val)
20        
21        traverse(root)
22        return result