Vertical Order of a Tree

Place a binary tree on a grid: the root is at row 0 and column 0, a node's left child is one row down and one column to the left, and its right child is one row down and one column to the right. Write vertical_order(root) that returns the tree's values column by column, from the leftmost column to the rightmost, as a list of lists.

Inside a column, list the values from the top row down. When two or more nodes share both a row and a column, list them from the smallest value to the largest. An empty tree gives [].

Each node is a Node with a value val and two children, left and right, which are None when missing. The provided build makes a tree from a list of values in level order, where None marks a missing child.

Examples

        3
      /   \
     9     20
          /  \
        15    7

vertical_order(build([3, 9, 20, None, None, 15, 7]))  # returns [[9], [3, 15], [20], [7]]
vertical_order(build([1, 2, 3, 4, 6, 5, 7]))  # returns [[4], [2], [1, 5, 6], [3], [7]]
vertical_order(build([]))  # returns []

The drawing shows the first tree: 3 and 15 are both in column 0, and 3 is higher up. In the second tree, 6 (the right child of 2) and 5 (the left child of 3) are both in row 2 and column 0, so the smaller one, 5, comes first.

Constraints

• 0 to 50,000 nodes, at most 600 levels deep.
• Values are integers, and different nodes can hold the same value.