107. Mirror a Binary Tree

Given a binary tree, swap the left and right child of every node (mirror it), then print the resulting tree using the same level-order token format as the input. 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). Print the mirrored tree the same way: level order, 'N' for absent nodes, omitting trailing children once no printed node in the queue has any children left to show.

Input: A single line of space-separated level-order tokens ('N' for missing children) describing the binary tree. Output: Print the mirrored tree's level-order tokens ('N' for absent nodes) on one line, omitting trailing children once no remaining queued node has any left to show.

1 <= number of nodes <= 10^5

This swap must happen at EVERY node, not just the root - swapping only the root's immediate children would leave the rest of the tree completely unmirrored.

Swap the left and right child of EVERY node in a binary tree, producing its mirror image. Brute force: Build an entirely new tree from scratch, recursively constructing each new node with children in swapped order - this works but allocates new nodes unnecessarily when the existing nodes' pointers can simply be swapped in place. Optimised: Swapping each node's existing left/right pointers directly (rather than constructing new nodes) mirrors the tree in place with no extra node allocation - a single recursive pass handles the whole tree.

Traverse the tree depth-first using a manually managed stack rather than either recursion or a breadth-first queue: pop a node, swap its children, then push whichever children exist. This avoids recursion's call-stack overflow risk just like the BFS approach, but its memory usage is bounded by the tree's height rather than its width - for a balanced or complete tree that's a logarithmic amount of extra space instead of the BFS queue's potentially linear width, making it the most memory-efficient option that's still safe from stack overflow on skewed trees. Time: O(n) Space: O(h)

Traverse the tree breadth-first with an explicit queue instead of recursion: dequeue a node, swap its left and right child pointers, then enqueue whichever (now-swapped) children exist. This avoids any recursion depth concerns entirely, but for a wide, bushy tree the queue can hold as many as roughly half the nodes at once (the widest level), so its memory usage scales with the tree's width rather than its height. Time: O(n) Space: O(w)

Rebuild the tree from the level-order tokens, then recursively visit every node and swap its left and right child pointers, recursing into both (now-swapped) subtrees; afterward, serialize the mirrored tree back into level-order token form via a BFS pass. This correctly mirrors every node, but relies on the language's call stack for recursion, which for a deeply skewed tree of up to 10^5 nodes risks a stack overflow. Time: O(n) Space: O(h)

1. Recursively swap the current node's left and right child pointers. 2. Recurse into what is now the left subtree (originally the right) and mirror it too. 3. Recurse into what is now the right subtree (originally the left) and mirror it too.

Time: O(n) - every node's pointers are swapped exactly once. Space: O(h) for the recursion stack; O(1) extra beyond that, since the mirroring happens via in-place pointer swaps.

Test a single-node tree (mirroring changes nothing), a tree where only one side has children (mirroring flips it entirely to the other side), and n=10^5 nodes for performance.

Be ready to connect this directly to the 'symmetric tree' check - a tree is symmetric exactly when it equals its own mirror image, so understanding mirroring deeply makes that related problem much easier to reason about.