Binary Tree Postorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Example 1:

Input: root = [1,null,2,3]

Output: [3,2,1]

Explanation: Consider a binary tree where the root is 1, the left child is null, the right child is 2, and the left child of 2 is 3. The postorder traversal would be [3, 2, 1].

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,6,7,5,2,9,8,3,1]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Could you implement both a recursive and an iterative solution? Also, how would you analyze the time and space complexity of each approach?

## Postorder Traversal of a Binary Tree

This problem asks us to implement a postorder traversal of a binary tree. Postorder traversal visits the left subtree, then the right subtree, and finally the root node itself.

### 1. Recursive Solution

The recursive solution is the most straightforward way to implement postorder traversal. We recursively call the function on the left and right subtrees before processing the current node.

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def postorder_recursive(root):
    if root is None:
        return []
    
    left_subtree = postorder_recursive(root.left)
    right_subtree = postorder_recursive(root.right)
    
    return left_subtree + right_subtree + [root.val]

# Example usage:
root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(postorder_recursive(root))

2. Iterative Solution

An iterative solution can be implemented using a stack. The key idea is to simulate the call stack of the recursive approach.

def postorder_iterative(root):
    if root is None:
        return []

    stack = [root]
    visited = set()
    result = []

    while stack:
        node = stack[-1]

        if node.left and node.left not in visited:
            stack.append(node.left)
        elif node.right and node.right not in visited:
            stack.append(node.right)
        else:
            result.append(node.val)
            visited.add(node)
            stack.pop()

    return result

# Example usage:
root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(postorder_iterative(root))

3. Morris Traversal (Optimal Iterative Solution)

Morris traversal is an in-order traversal algorithm that does not use recursion or a stack. This makes it an optimal solution in terms of space complexity for certain traversals, and can be adapted for postorder traversal as well.

def reverse_linked_list(start, end):
    prev = None
    curr = start
    while curr != end:
        next_node = curr.right
        curr.right = prev
        prev = curr
        curr = next_node
    return prev

def postorder_morris(root):
    result = []
    dummy = TreeNode(0)
    dummy.left = root
    current = dummy

    while current:
        if current.left is None:
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right

            if predecessor.right is None:
                predecessor.right = current
                current = current.left
            else:
                predecessor.right = None
                temp = current.left
                tail = reverse_linked_list(temp, current)
                node = tail
                while node:
                    result.append(node.val)
                    node = node.right
                reverse_linked_list(tail, temp)
                current = current.right

    return result

root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(postorder_morris(root))

Big O Analysis:

Recursive Solution:

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
• Space Complexity: O(H), where H is the height of the tree, due to the call stack. In the worst case (skewed tree), H can be N, resulting in O(N) space complexity. In the best case (balanced tree), H would be log(N).

Iterative Solution:

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
• Space Complexity: O(N), in the worst case, when the stack contains all nodes in a skewed tree.

Morris Traversal Solution:

• Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited twice.
• Space Complexity: O(1), constant space. We are not using any additional data structures that scale with the input size.

Edge Cases:

• Empty Tree: If the root is None, the function should return an empty list. Both the recursive and iterative solutions handle this case correctly.
• Single Node Tree: If the tree contains only one node, the function should return a list containing the value of that node.
• Skewed Tree (left or right): The algorithm should correctly traverse a tree where all nodes are on the left or right side.
• Large Tree: The algorithm should be efficient enough to handle a tree with up to 100 nodes, as specified in the constraints.