112. Left View of a Binary Tree

Given a binary tree, print its left view - the leftmost 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 ('N' for missing children) describing the binary tree. Output: Print the left 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 'right view' problem - swapping 'first per level' for 'last per level' (or 'left-first' for 'right-first' DFS) converts one into the other directly.

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

For every depth d from 0 up to the tree's height, perform a fresh traversal of the whole tree that tracks the current depth and records the first node encountered at depth d, discarding all other nodes at that depth. This directly produces the correct leftmost-node answer for each level, but redoing a full traversal once per level means nodes near the root get revisited for every level below them. Time: O(n*h) Space: O(h)

Traverse the tree level by level using a queue (BFS): process one full level at a time, and record the value of the first node dequeued in each level as that level's left-view entry before enqueueing its children. Because the whole tree is visited exactly once instead of once per level, this eliminates the repeated re-traversal of the brute-force approach, at the cost of a queue that can hold up to an entire level's worth of nodes (up to n/2 for a wide tree). Time: O(n) Space: O(n)

Do a single depth-first traversal that always visits the left child before the right child, carrying along the current depth and a running 'maximum depth visited so far'. The first time the traversal reaches a new depth (current depth equals maximum depth visited so far, meaning no node at this depth has been recorded yet), record that node's value - since left is always explored before right, this guarantees the recorded node is the leftmost one at that depth. This achieves the same linear time as the BFS approach but needs no queue at all, only the recursion stack, so its extra space is bounded by the tree's height rather than its width - much smaller for wide, shallow trees. Time: O(n) Space: O(h)

1. Do a level-order (breadth-first) traversal. 2. For each level, record the FIRST node processed at that level - that's the leftmost 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, a level whose leftmost visible node is actually a right child (because the true left child is missing), and n=10^5 nodes for performance.

Be ready to present BOTH the BFS (level-by-level, take the first) and recursive DFS (left-first, first-at-depth) solutions, and to clearly distinguish this from the right-view problem, which is its exact mirror.