110. Postorder Traversal of a Binary Tree

Given a binary tree, print its postorder traversal (left subtree, then right subtree, then the node), space-separated. The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: A single line of space-separated level-order tokens ('N' for missing children) describing the binary tree. Output: Print the postorder traversal (left subtree, then right subtree, then the node) space-separated on one line.

1 <= number of nodes <= 10^5

Postorder is the traversal of choice whenever a computation needs children's RESULTS before it can compute the parent's own result - this connects directly to nearly every 'bottom-up' tree DP problem in this category.

Visit every node of a binary tree in the order: left subtree, then right subtree, then the node itself. Brute force: There's no meaningfully different alternative - postorder traversal IS the direct definition; the only choice is recursive versus iterative (using one or two stacks) implementation. Optimised: An iterative version can use two stacks: push nodes onto the first stack in a modified preorder (node, right, left), then pop everything from the first stack directly onto a second stack, whose final pop order is exactly postorder - a clever trick for avoiding more complex single-stack bookkeeping.

Use one explicit stack and repeatedly push nodes down the current node's left spine. When a node has no further left child to push, check whether it has an unvisited right child: if so, move to that right child and continue pushing down its left spine; if not, or if the right child was already the most recently visited node, pop and visit the current node, then treat it as the last-visited node before continuing with the new stack top. This achieves the same traversal using only one stack instead of two, at the cost of a bit more bookkeeping to know when a node's children have both already been handled. Time: O(n) Space: O(h)

Push the root onto a first stack. Then repeatedly pop a node from this first stack, push that node onto a second stack, and push its left child (if any) followed by its right child (if any) onto the first stack; this visits nodes in a root-right-left order on the first stack. Once the first stack is empty, popping the second stack from top to bottom yields exactly the postorder sequence, because the second stack ends up holding nodes in the reverse of that root-right-left visitation order. Time: O(n) Space: O(n)

Directly implement the recursive definition of postorder: for the current node, first recursively traverse its left subtree, then recursively traverse its right subtree, and only after both are done, visit (print) the current node itself. The base case is a null node, which does nothing. This mirrors the definition exactly, using the language's own call stack to keep track of pending work. Time: O(n) Space: O(h)

1. Recursively traverse the entire left subtree first. 2. Recursively traverse the entire right subtree. 3. Visit (print) the current node LAST.

Time: O(n) - every node is visited exactly once. Space: O(h) for the recursion stack (or O(n) for the two-stack iterative approach).

Test a single-node tree (output is just the root), a fully skewed tree, and n=10^5 nodes for performance.

Be ready to explain WHY the node is visited LAST here - this ordering is precisely what makes postorder the natural choice whenever you need to process CHILDREN before their PARENT (like computing subtree sums, heights, or safely deleting a tree node by node).