Skills101
← All coding problems

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).

Loading editor…

Log in to run and submit your code — it's free.