407. Reverse Level Order Traversal

Given a binary tree, print its nodes level by level from the deepest level up to the root level (the reverse of normal level order); within each level, print nodes left to right. Print all values in this order, space-separated on one line. 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 all node values space-separated on one line, ordered from the deepest level up to the root, left to right within each level.

1 <= number of nodes <= 10^5

This is a small, simple variation on standard level-order traversal - recognizing it as 'collect levels normally, print them backward' avoids overcomplicating what's really a straightforward post-processing step.

Print a binary tree level by level, but starting from the DEEPEST level and working back up to the root. Brute force: There isn't really a slower meaningful alternative - collecting levels normally and then reversing just the ORDER OF LEVELS (not the values within each level) IS the natural, direct approach. Optimised: Since the requirement is only to reverse the ORDER LEVELS APPEAR IN (not the order of values within each level), a simple normal BFS followed by printing the collected level-lists in reverse achieves this directly - no need for any more complex traversal logic.

Do one breadth-first traversal starting from the root, but at each node enqueue the right child before the left child (the opposite of normal level order), and push every dequeued node's value onto a stack instead of a list. Because the traversal order is deepest-level-last and right-before-left within a level, popping the entire stack at the end yields the levels bottom-to-top with each level's nodes emerging left-to-right automatically, with no separate list-of-levels bookkeeping or explicit reversal step needed. Time: O(n) Space: O(n)

Perform one standard breadth-first traversal, collecting the nodes of each depth into its own list (a list of lists), the same way a normal level-order traversal would. Once the BFS finishes, simply reverse the outer list of levels and print each level's nodes left to right. This does a single pass over the tree instead of one pass per level, which is a real improvement over the repeated-traversal brute force, though it needs to hold the fully separated level structure in memory before reversing. Time: O(n) Space: O(n)

First find the tree's height with one traversal, then for every level from the deepest up to the root, run a separate traversal from the root that only prints nodes exactly at that target depth (the standard 'recurse and decrement depth counter' technique). This is correct because repeating a depth-limited traversal for each level visits and prints exactly the nodes at that level, but it re-walks large portions of the tree once per level, which is quadratic in the worst case for skewed trees. Time: O(n * h) worst case O(n^2) Space: O(h)

1. Perform a normal level-order (breadth-first) traversal, collecting each level's values into its own separate list, in the usual top-to-bottom order. 2. Once every level's list has been collected, print them starting from the LAST (deepest) level's list and ending with the FIRST (root's) level's list. 3. Within each individual level, the left-to-right order stays unchanged - only the ORDER OF LEVELS themselves gets reversed.

Time: O(n) - one BFS pass to collect levels, plus O(number of levels) to print them in reverse (which is bounded by n anyway). Space: O(n), for storing all levels' collected values before printing.

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

Be precise that only the LEVEL ORDER reverses, not the left-to-right order WITHIN each level - a common point of confusion that's worth clarifying explicitly if the problem statement is ever ambiguous.