Binary Tree Postorder Traversal

Recursive postorder is direct: if node is null return; traverse left, traverse right, then append node.val. The interesting part is iterative traversal because popping a node immediately would emit it before its children. One robust approach uses a stack and lastVisited pointer. Walk left, pushing nodes. Peek the stack; if its right child exists and was not last visited, move right, otherwise pop and emit it, setting lastVisited. Another approach uses two stacks, but it costs more memory. State the child-order invariant so an interviewer can see why a node is emitted only after both subtrees. Test null root, one node, left-only and right-only chains, and a node with two children. Every node is pushed and popped a constant number of times, so time is O(n) and auxiliary stack space is O(h), reaching O(n) for a skewed tree.