115. Bottom View of a Binary Tree

Assign every node a horizontal distance (hd): the root has hd 0, a left child has hd = parent's hd - 1, a right child has hd = parent's hd + 1. Given a binary tree, for every distinct horizontal distance that occurs, print the value of the node that would be seen from directly below - among all nodes at that hd, prefer the greatest depth, and break ties between equally-deep nodes by taking whichever comes later in level order. Print the values ordered by ascending horizontal distance, 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 an absent child). Output: Print the bottom view values ordered by ascending horizontal distance, space-separated on one line.

1 <= number of nodes <= 10^5

The 'overwrite on every visit' trick relies ENTIRELY on level-order's specific visiting guarantees (shallower-first, left-to-right within a level) - it wouldn't correctly work with a DFS-based traversal without extra depth tracking.

Imagine looking straight up at a binary tree from directly below - print the one node value visible at each horizontal position. Brute force: Compute the horizontal distance and depth of every node directly, then for each distinct hd, manually find the deepest (and latest, on ties) node - this works but requires extra bookkeeping to explicitly track and compare depths, when a level-order traversal's natural visiting order already gives you this 'for free' via simple overwriting. Optimised: Because level-order traversal visits nodes in exactly the right priority order (shallower first, and left-to-right within a level), simply overwriting the recorded value for each hd as you go automatically ends up keeping the deepest, latest-visited node at each hd - no explicit depth comparison logic is needed at all.

Perform one level-order BFS traversal while maintaining a hashmap from horizontal distance to the most recently seen value at that horizontal distance, simply overwriting the map entry every time a node with that horizontal distance is dequeued. Because BFS naturally processes nodes level by level (and left to right within a level), a later overwrite always corresponds to an equal-or-greater depth and later level-order position, so the map entry after the full traversal is automatically the correct bottom-view value for that horizontal distance with no separate post-processing step needed - just a single pass and a final sorted read-out by horizontal distance. Time: O(n) Space: O(n)

Do one level-order BFS traversal, and for every node visited record its (horizontal distance, depth, value) as an entry, grouping all entries by horizontal distance (for example, in a hashmap of lists). After the traversal completes, do one post-processing pass over each horizontal-distance group to pick the entry with the greatest depth (using later level-order position as a tie-breaker). This is a big improvement over repeating full traversals, since the tree is only scanned once, but it still requires an extra bookkeeping pass afterward to resolve which entry 'wins' within each group. Time: O(n) Space: O(n)

First determine the full range of horizontal distances present in the tree. Then, for each distinct horizontal distance value, perform a complete traversal of the tree to find the node at that horizontal distance with the greatest depth (breaking ties by later level-order position), recording its value. This correctly determines the bottom view definition for each horizontal distance independently, but repeating a full tree scan once per distinct horizontal distance means the total work can grow close to quadratic in the number of nodes. Time: O(n * number of distinct horizontal distances) Space: O(n)

1. Assign every node a horizontal distance (hd): root is 0, left child is parent's hd - 1, right child is parent's hd + 1. 2. Do a level-order (breadth-first) traversal, and for each hd, keep OVERWRITING your recorded value with whatever node you encounter at that hd. 3. Since level-order visits shallower nodes first, the LAST write for any given hd naturally ends up being the deepest node there (and among equally deep nodes, whichever comes later in level order, exactly matching the required tie-break). 4. Print the recorded values ordered by ascending horizontal distance.

Time: O(n log n) if using a sorted map keyed by hd (or O(n) with a plain hashmap plus a final sort of the distinct hd values, since hd values only span a limited range). Space: O(n), for the map from horizontal distance to recorded value, plus the traversal queue.

Test with a single-node tree, multiple nodes sharing the same horizontal distance at different depths (the deepest one wins), and a tree with 10^5 nodes for performance.

Be ready to contrast this with 'Top View' (which would need the FIRST write at each hd to be kept, not the last) - a small but crucial difference in a very similarly-shaped problem.