Top View of Binary Tree
mediumTrees & BST II+20 XPTime limit 2s
Look at the tree from above. In every column you see only the node closest to the top. Print the values you see, from the leftmost column to the rightmost.
Columns. Put the root in column 0. A left child is one column to the left of its parent (column − 1), a right child one column to the right (column + 1). In each column you see the node on the highest level (smallest depth); if two nodes of that level share the column, you see the one that comes first in level order (the more left one in the drawing).
Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is
3
/ \
9 20
/ \
15 7
Input: one tree.
Output: the visible values on one line, left to right, or empty for an empty tree.
Constraints: 0 ≤ nodes ≤ 10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.
Think about it: a plain DFS can reach a deep node before a shallow one in the same column. BFS visits nodes level by level, left to right — so the first node you meet in each column is exactly the one you see. Store column → value in a map and keep the first.
Sample input 1
1 2 3 null 4 5 6
Sample output 1
2 1 3 6
Sample input 2
1 2 3 4 5 6 7
Sample output 2
4 2 1 3 7
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).