145. Binary Tree Postorder Traversal

This problem asks for a postorder traversal of a binary tree. Postorder traversal visits the nodes in the order: left subtree, right subtree, then root. We'll explore three solutions: recursive, iterative using a stack, and iterative using Morris traversal.

Solution 1: Recursion

This is the most straightforward approach. A recursive function visits the left subtree, then the right subtree, and finally adds the root node's value to the result.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack. In the worst case (a skewed tree), H can be N. In the best case (a balanced tree), H is log₂N.

Code:

Python:

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        def dfs(node):
            if node:
                dfs(node.left)
                dfs(node.right)
                result.append(node.val)
        dfs(root)
        return result

Java:

class Solution {
    List<Integer> result = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        dfs(root);
        return result;
    }
    private void dfs(TreeNode node) {
        if (node != null) {
            dfs(node.left);
            dfs(node.right);
            result.add(node.val);
        }
    }
}

(Other languages like C++, Go, TypeScript, and Rust would follow similar recursive structures.)

Solution 2: Iterative Approach with Stack

This solution avoids recursion by using a stack to simulate the recursive calls. We push nodes onto the stack in the reverse order of how we would visit them recursively (right child, then left child). Then, we pop the nodes from the stack and add their values to the result.

Time Complexity: O(N) – Each node is visited and processed once.

Space Complexity: O(N) – In the worst case (a skewed tree), the stack can hold up to N nodes.

Code:

Python:

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        stack = []
        curr = root
        while curr or stack:
            if curr:
                stack.append(curr)
                curr = curr.left
            else:
                temp = stack.pop()
                curr = temp.right
                result.append(temp.val)
        return result
 

Java:

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode temp = stack.pop();
                curr = temp.right;
                result.add(temp.val);
            }
        }
        return result;
    }
}

(Adaptations for C++, Go, TypeScript, and Rust would use their respective stack implementations.)

Solution 3: Morris Traversal (Space-Optimized)

Morris traversal is an elegant technique that performs tree traversal without using recursion or a stack, achieving O(1) space complexity. The idea is to use the tree's structure itself to keep track of the traversal. It involves modifying the tree temporarily by adding links, then restoring the original structure. The algorithm is more complex than the previous two. Because it needs to modify the tree structure, it may not be suitable for all use cases where the input tree's original structure is critical.

Time Complexity: O(N)

Space Complexity: O(1)

Code (Python Example): Implementation details are significantly more involved and vary across languages. This is a conceptual outline; refer to specialized resources for detailed, correct implementations of Morris postorder traversal in different languages. It's considerably more challenging to implement accurately.

# (Implementation is significantly more complex and omitted for brevity; 
# refer to specialized resources for correct implementation in Python or other languages.)
 

In summary, the recursive solution is the simplest and most readable, but it has a space complexity that depends on the tree's height. The iterative stack-based solution offers better space performance in the worst-case scenario, while Morris traversal is the most space-efficient but also the most complex to implement. Choose the solution that best balances readability, performance requirements, and the constraints of your specific application.