408. Diagonal Traversal of a Binary Tree

A binary tree's diagonals are formed like this: the root starts the first diagonal; from any node, following a right child stays on the same diagonal, while following a left child starts a new diagonal one step later. Print every diagonal's values, one diagonal after another starting with the root's diagonal, space-separated on one line - within a diagonal, print nodes in the order a top-to-bottom, left-to-right traversal would discover them. 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 describing the binary tree ('N' marks an absent child). Output: Print every diagonal's values, one diagonal after another starting from the root's diagonal, space-separated on one line.

1 <= number of nodes <= 10^5

A node with NO left child never starts a new diagonal of its own - it simply extends whichever diagonal its parent (or a right-ancestor) already belongs to, an important detail for correctly identifying diagonal boundaries.

Group a binary tree's nodes into 'diagonals', where following a right child keeps you on the same diagonal, but following a left child starts a brand new diagonal - then print each diagonal's values in order. Brute force: Compute a 'diagonal number' for every node via a full recursive traversal (incrementing the diagonal number on every left turn) and group nodes by that number - this works but requires an extra data structure to bucket and later print each diagonal group, more bookkeeping than the direct queue-based approach. Optimised: The queue-of-starting-points technique naturally processes diagonals in the correct top-to-bottom order without needing to separately track or sort diagonal 'levels' - each right-chain walk directly produces one diagonal's full node list in the correct left-to-right order within that diagonal.

Recursively walk the tree, passing down a diagonal id (root starts at 0, a right child keeps the parent's diagonal id, a left child gets parent's id + 1), and append each node's value into a hash map keyed by diagonal id, recursing into the left child before the right child. Because right children are processed before returning to explore the corresponding left subtree, values naturally land in each diagonal bucket in top-to-bottom, left-to-right order. Afterward, sort the map's keys and print each bucket in order. This works but needs an explicit sort of diagonal ids and risks deep recursion on skewed trees. Time: O(n log n) Space: O(n)

This is the same queue-driven idea as the better approach, but recognize that visiting every node and printing every value is unavoidable, so O(n) time is already optimal - the remaining win is space. Instead of accumulating a separate list per diagonal before printing (which needs O(n) map storage), stream each diagonal's values straight to the output as its right-chain is walked, and only keep a queue holding the currently-known left children (the frontier), whose total size across the whole run is bounded by n but never needs a diagonal-indexed structure. This keeps the same O(n) time while using only the minimum bookkeeping needed for the traversal frontier rather than a full auxiliary map. Time: O(n) Space: O(n)

Use a queue seeded with the root. Repeatedly dequeue a node and, in an inner loop, follow its right-child chain, printing every node's value as you go and enqueueing each left child you encounter along the way (those left children start the next diagonal). This processes one full diagonal per outer iteration in the exact required order, is entirely iterative (no recursion, no risk of stack overflow on skewed trees), and removes the need to bucket values into a map keyed by diagonal id, since output is produced directly. Time: O(n) Space: O(n)

1. Use a queue holding 'diagonal starting points', beginning with just the root. 2. For each starting point dequeued, walk it and ALL its right-descendants (that's the entire diagonal), printing them - while walking, every LEFT child you encounter along the way gets enqueued as the start of a FUTURE diagonal. 3. Process starting points strictly in the order they were enqueued, so earlier diagonals always print completely before later ones begin.

Time: O(n) - every node is visited (and printed) exactly once across all diagonal walks combined. Space: O(n) in the worst case, for the queue of diagonal-starting-points (bounded by the number of left-children in the tree).

Test with a single-node tree, a tree made only of right children (everything falls on one diagonal), a tree made only of left children (every node starts its own diagonal), and a tree with 10^5 nodes for performance.

Be ready to draw out a small tree and manually trace which nodes belong to which diagonal - this problem is much easier to get right with a clear mental picture than by reasoning about it purely abstractly.