Vertical Order Traversal
hardTrees & BST II+40 XPTime limit 2s
Give every node a position: the root is at row 0, column 0; a left child is one row down and one column left (row + 1, column − 1); a right child is one row down and one column right (row + 1, column + 1).
Print the tree column by column, from the leftmost column to the rightmost. Inside a column, list nodes from the top row down; when several nodes share the same row and column, list them in increasing order of value.
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: one line per column (left to right) with that column's values, or empty for an empty tree.
Constraints: 0 ≤ nodes ≤ 10⁴, −1000 ≤ value ≤ 1000. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.
Think about it: traverse the tree (BFS or DFS) and record (column, row, value) for every node. Then sort these triples — the sort order does all the work — and group them by column. Nodes in the same row and column really happen: in 1 2 3 4 6 5 7, the values 6 and 5 both sit at row 2, column 0.
Sample input 1
3 9 20 null null 15 7
Sample output 1
9 3 15 20 7
Sample input 2
1 2 3 4 6 5 7
Sample output 2
4 2 1 5 6 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).