105. Level Order Traversal of a Binary Tree

Given a binary tree, print the values of its nodes in level order (breadth-first, top to bottom, left to right within a level), 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 all node values in breadth-first, level-by-level, left-to-right order, space-separated on one line.

1 <= number of nodes <= 10^5

'N' tokens in the input represent absent nodes and must NEVER themselves be enqueued or printed - only real, non-null nodes participate in the traversal.

Visit every node of a binary tree level by level, from top to bottom, left to right within each level. Brute force: There isn't a meaningfully different 'brute force' here - a queue-based BFS IS the direct, standard way to achieve level-order traversal. Optimised: A simple queue naturally processes nodes in exactly the right order (shallower nodes dequeued before deeper ones, since they were enqueued first) - no extra bookkeeping about depth is even needed unless you want to separate output BY level.

First parse the level-order tokens into an actual linked tree structure with left/right child pointers, then perform a standard breadth-first traversal using a queue: dequeue a node, print its value, enqueue its children, and repeat. This directly produces nodes in level order without needing a depth-indexed map, but it still does two full passes over the data - one to build the tree, one to traverse it. Time: O(n) Space: O(n)

Parse the tokens into a tree, then do a DFS traversal that, for every node visited, appends its value into a list keyed by that node's depth (a map from depth to list of values). Once the DFS finishes, iterate over the depths in increasing order and print each list's values. This correctly separates nodes by level, but it requires building an entire auxiliary map and treats the actual level ordering as a distinct step performed after traversal rather than during it. Time: O(n) Space: O(n)

Since the input tokens are already given in level order, use a single queue to consume the token stream and print each value as it is dequeued, enqueuing its two children tokens (if not 'N') in that same step, so tree construction and traversal happen simultaneously in one pass rather than as two separate stages. This removes the need to fully materialize the tree in memory before traversing it, cutting the work down to exactly one linear scan of the input with only the current queue held in memory. Time: O(n) Space: O(w), w = widest level

1. Use a queue, starting with just the root inside it. 2. Repeatedly dequeue a node, print it, and enqueue its non-null children (left then right). 3. Continue until the queue is empty.

Time: O(n) - every node is enqueued and dequeued exactly once. Space: O(n) in the worst case (a very wide tree, like a complete binary tree's bottom level), for the queue.

Test a single-node tree, a tree with 'N' tokens scattered across levels (they must never themselves be printed or enqueued), and n=10^5 nodes for performance.

This is a foundational traversal used as a building block in dozens of other tree problems (top/bottom/left/right view, zig-zag traversal, and more) - make sure the basic queue-based implementation feels completely automatic.