Binary Tree Postorder Traversal

Intuition

Postorder (left, right, node) is the exact reverse of a modified preorder that visits node, right, then left. That modified order is easy to generate iteratively with a single stack: pop a node, record it, then push its left child before its right child so the right child is processed first. Collecting values this way gives us node-right-left, and reversing that list at the end produces the desired left-right-node order. This sidesteps the trickier bookkeeping of a direct postorder stack, which must remember whether a node's right subtree has already been handled.

Algorithm walkthrough

1. 1Return an empty list immediately when the root is null.
2. 2Push the root onto a stack and prepare an output list.
3. 3While the stack is not empty, pop a node and append its value; this builds a node-right-left sequence.
4. 4Push the node's left child first, then its right child, so the right child is popped before the left.
5. 5After the loop ends, reverse the output list to turn node-right-left into left-right-node.
6. 6Return the reversed list as the postorder result.

Implementation

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