Tree Vertical Order Keys

Problem

Group the values of a binary tree by vertical column.

tree is a level-order list with None marking missing nodes. Assign each node a horizontal distance (root 0, left child one less, right child one more) and collect nodes column by column, ordered by level and then left to right within a column.

Return a list of columns from leftmost to rightmost.

Hint

BFS visits nodes level by level, which matches the required ordering inside each column.

Test cases

case 1

in: [[1,2,3,4,5,6,7]]

expected: [[4],[2],[1,5,6],[3],[7]]

case 2

in: [[]]

expected: []

case 3

in: [[1,2]]

expected: [[2],[1]]

case 4

in: [[1,2,3]]

expected: [[2],[1],[3]]

Starter codePython

def vertical_order(tree):
    # Your code here
    pass

4 test cases · run your code against them in the editor