114. Top 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 topmost (smallest-depth) node at that distance; if several nodes share both the smallest depth and the same hd, use whichever is encountered first 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 top view values ordered by ascending horizontal distance, space-separated on one line.

1 <= number of nodes <= 10^5

Both top view and bottom view rely entirely on level-order's specific traversal guarantees (shallower nodes visited before deeper ones) - this single shared insight underlies both problems, just applied with opposite recording rules.

Imagine looking at a binary tree from directly above - print the topmost node visible at every horizontal position. Brute force: Compute hd and depth for every node directly, then for each distinct hd manually find whichever node has the SMALLEST depth - this works but requires extra explicit depth-comparison bookkeeping, when level-order's natural visiting order already gives this 'for free'. Optimised: This is the EXACT mirror of the 'bottom view' technique - instead of overwriting on every visit (which keeps the LAST/deepest), you only write ONCE per hd (keeping the FIRST/shallowest) - the same level-order traversal, just a one-word change in the recording rule.

Do a single BFS from the root, tracking each node's horizontal distance (root=0, left child = parent-1, right child = parent+1). Maintain a hashmap from hd to the first value encountered at that hd; because BFS visits shallower nodes before deeper ones, the first insertion for any given hd is automatically the topmost node, so later nodes at the same hd are simply skipped. After one traversal, sort the hashmap's keys (hd values) in ascending order and print their associated values. This replaces the repeated traversals of brute force with just one, at the cost of a sort over the number of distinct horizontal distances. Time: O(n log n) Space: O(n)

Same single BFS as the better approach, but instead of a hashmap keyed by (possibly negative) hd values, use a plain array of size 2n+1 indexed by hd+n (shifting all horizontal distances into a non-negative range, since hd can never exceed the node count in magnitude). Recording 'first node seen' at each shifted index during BFS costs O(1) per node with no hashing overhead, and because array indices are already in ascending hd order, the final answer can be read off with one linear scan and no sort at all. Time: O(n) Space: O(n)

For every distinct horizontal distance value that could occur (ranging from -(n-1) to (n-1)), perform a fresh BFS over the entire tree tracking (node, hd, depth) and find the shallowest node whose hd matches that particular value (breaking ties by level-order/BFS discovery order). Repeating a full traversal once per candidate hd value is correct since it directly implements the definition, but it revisits the whole tree many times over. Time: O(n * range of hd) which can be O(n^2) Space: O(n)

1. Assign every node a horizontal distance (hd), just like in bottom view. 2. Do a level-order traversal, and for each hd, record ONLY the FIRST node encountered there (never overwrite it again) - since level order visits shallower nodes first, the first node seen at any hd is guaranteed to be the topmost. 3. Print the recorded values ordered by ascending horizontal distance.

Time: O(n log n) with a sorted map keyed by hd (or O(n) with a hashmap plus a final sort of the distinct hd values). Space: O(n), for the hd-to-value map and the traversal queue.

Test with a single-node tree, multiple nodes sharing the same horizontal distance and depth (the one encountered first in level order wins), and a tree with 10^5 nodes for performance.

Be ready to state the single, precise distinction between top view and bottom view (first-write-wins versus last-write-wins) - conflating the two is an extremely common and easy-to-make mistake under interview pressure.