113. Right View of a Binary Tree

Given a binary tree, print its right view - the rightmost node visible at every level, from top to bottom, 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 describing the binary tree ('N' marks a missing child): the first token is the root, then each dequeued node's left-child token followed by its right-child token. Output: Print the right view values, space-separated on one line, from the topmost level down to the bottom.

1 <= number of nodes <= 10^5

This is the mirror image of the 'left view' problem - swapping which side ('last per level' vs 'first per level', or 'right-first' vs 'left-first' DFS) converts one into the other directly.

Imagine looking at a binary tree from directly on its right side - print the one node visible at each level. Brute force: Recursively walk LEFT-first and record a node only if a DEEPER node hasn't already been recorded at that depth - this actually produces the LEFT view instead; a right view needs the mirror approach (walk right-first, or take the last node per level in a left-to-right BFS). Optimised: A level-order traversal naturally groups nodes by level, so simply keeping the LAST node processed within each level's group directly gives the right view - alternatively, a recursive right-first DFS that records a node only the FIRST time its depth is reached also works, since visiting right children first guarantees the rightmost node at each depth is seen first.

Rebuild the tree from the level-order tokens, then run a standard breadth-first traversal level by level using a queue, collecting every node's value into a list for that level before moving to the next depth. Once a level's full list is collected, its last element is the rightmost, visible node, so append it to the answer. This works correctly but wastefully retains every value at every level even though only the last one per level is ever used. Time: O(n) Space: O(n)

Do a depth-first traversal that always visits the right child before the left child, tracking the current depth as you recurse. The first time a given depth is reached, the node encountered is guaranteed to be the rightmost node at that depth (because right subtrees are always explored first), so append its value to the result only when the current depth equals the number of results already recorded. This still visits every node once but the auxiliary storage is now just the recursion stack, bounded by the tree's height rather than the queue-based approach's potential need to hold an entire wide level at once, which is a real memory win for balanced or bushy trees. Time: O(n) Space: O(h)

Still traverse level by level with a queue, but instead of collecting a full list of values for the level, just record the current queue size at the start of each level and overwrite a single 'last seen value' variable as you dequeue each node in that level; once the level's fixed count of dequeues is done, that variable holds the rightmost node and gets appended to the result. This does the same amount of traversal work as the brute-force version but avoids materializing an extra list per level, trading it for a single reused variable. Time: O(n) Space: O(n)

1. Do a level-order (breadth-first) traversal. 2. For each level, record the LAST node processed at that level - that's the rightmost node visible from that level. 3. Print these recorded values, one per level, top to bottom.

Time: O(n) - every node is visited exactly once, whether via BFS or DFS. Space: O(n) in the worst case for the BFS queue (or O(h) for a DFS recursion stack).

Test a single-node tree (n=1, output is just the root), a tree where a level's rightmost visible node is actually a left child (because the true right child is missing), and n=10^5 nodes for performance.

Be ready to present BOTH the BFS (level-by-level, take the last) and recursive DFS (right-first, first-at-depth) solutions - interviewers often ask for both to check comfort with multiple traversal strategies.