Problem Description

Given the root of a binary tree, return the postorder traversal of its nodes' values. In postorder traversal, you visit the left subtree first, then the right subtree, and finally the root node itself.

• The input is a binary tree represented by its root node, root.
• Your output should be a list/array of integers representing the values of the nodes in postorder.
• Each node in the tree contains an integer value.
• You may assume the tree contains at least 0 or more nodes (the tree may be empty).

Thought Process

The problem asks for a specific order of visiting nodes in a binary tree: left subtree, then right subtree, then the node itself. This is known as postorder traversal. The most straightforward way is to use recursion, as the traversal order naturally fits the recursive structure of trees. However, recursion uses the call stack, which may not be ideal for very deep trees. An iterative approach is also possible, but it requires careful management of the traversal order using a stack.

Initially, one might consider traversing the tree and storing the nodes in the order they are visited. However, to match the postorder requirement, we need to make sure we process the left and right children before the parent node. Recursion handles this naturally, but with iteration, we need to simulate the call stack.

Solution Approach

Let's break down the two main approaches to solve this problem:

• Recursive Approach:
  • Define a helper function that takes a node as input.
  • If the node is null, return immediately.
  • Recursively traverse the left subtree.
  • Recursively traverse the right subtree.
  • Append the node's value to the result list.

  This approach closely follows the definition of postorder traversal. The function calls itself for left and right children, ensuring that the parent node is processed last.

• Iterative Approach:
  • Use a stack to simulate the recursion.
  • Push the root node onto the stack.
  • Pop a node from the stack, and prepend (or push onto a second stack) its value to the result list.
  • Push the left child (if any), then the right child (if any) onto the stack.
  • Repeat until the stack is empty.
  • Reverse the result list at the end (if using a single stack), as this process creates a "root-right-left" order, which is the reverse of postorder.

  This approach is a bit trickier, as you must carefully manage the order in which nodes are processed. Using two stacks or reversing the result at the end makes sure the output is in postorder.

For both approaches, we traverse each node exactly once, and each node's value is added to the result in the correct order.

Example Walkthrough

Let's use the following binary tree as an example:

        1
         \
          2
         /
        3
  

Step-by-step postorder traversal:

1. Start at root node 1.
2. Left child of 1 is null, so move to right child 2.
3. At node 2, left child is 3. Traverse left to 3.
4. Node 3 has no children, so add 3 to the result.
5. Back to node 2, right child is null. Now add 2 to the result.
6. Back to root node 1, both children are processed. Add 1 to the result.

Final output: [3,2,1]

Time and Space Complexity

• Time Complexity:
  • Both recursive and iterative approaches visit each node exactly once.
  • Therefore, the time complexity is O(n), where n is the number of nodes in the tree.
• Space Complexity:
  • Recursive approach: The maximum depth of the recursion stack is O(h), where h is the height of the tree. In the worst case (completely unbalanced tree), h = n.
  • Iterative approach: The stack can hold up to O(h) nodes at any time.
  • The result list uses O(n) space for the output.
• Brute-force approach: There is no meaningful brute-force for tree traversal, as every node must be visited at least once. Thus, O(n) is optimal.

Summary

In this problem, we performed a postorder traversal of a binary tree, visiting each node's left subtree, right subtree, and then the node itself. Both recursive and iterative solutions are efficient and visit each node exactly once. The recursive approach is more intuitive and concise, while the iterative approach avoids recursion and is more explicit about stack usage. Understanding traversal orders and how to implement them both recursively and iteratively is fundamental for working with binary trees.

Code Implementation

# 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):
        result = []
        def dfs(node):
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            result.append(node.val)
        dfs(root)
        return result
      

/**
 * 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:
    void dfs(TreeNode* node, vector<int>& result) {
        if (!node) return;
        dfs(node->left, result);
        dfs(node->right, result);
        result.push_back(node->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        dfs(root, result);
        return result;
    }
};
      

/**
 * 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<>();
        dfs(root, result);
        return result;
    }
    private void dfs(TreeNode node, List<Integer> result) {
        if (node == null) return;
        dfs(node.left, result);
        dfs(node.right, result);
        result.add(node.val);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const result = [];
    function dfs(node) {
        if (!node) return;
        dfs(node.left);
        dfs(node.right);
        result.push(node.val);
    }
    dfs(root);
    return result;
};