Group Binary Tree Nodes by Vertical Column, Top to Bottom and Left to Right

Given a binary tree, report its node values column by column. The root is at column 0 and row 0. A left child is one column to the left of its parent (column minus 1), a right child is one column to the right (column plus 1), and each child is one row below its parent.

Return one list per column, from the leftmost column to the rightmost. Within a column, list values from the top row to the bottom row. When two or more nodes share both a row and a column, list them in left-to-right order within that row.

Function Signature

def vertical_columns(tree: list[int | None]) -> list[list[int]]:

Rules

• Input format. tree is the level-order serialization of the tree. tree[0] is the root; after it, entries are consumed two at a time as the left child and then the right child of each non-null node, in the order those nodes appear. None marks a missing child, children of missing nodes are not listed, and trailing None entries may be omitted. An empty list is an empty tree.
• Left-to-right order within a row is the order in which nodes of that row appear in the level-order serialization.
• Output one list for each column that contains at least one node; an empty tree returns [].

Constraints

• 0 <= number of nodes <= 100
• -100 <= node value <= 100; values may repeat.

Examples

Example 1

Input: tree = [3, 9, 20, None, None, 15, 7]

Output: [[9], [3, 15], [20], [7]]

Explanation: 9 is at column -1; 3 (row 0) and 15 (row 2, left child of 20) are at column 0; 20 is at column 1; 7 is at column 2.

Example 2

Input: tree = [3, 9, 8, 4, 0, 1, 7]

Output: [[4], [9], [3, 0, 1], [8], [7]]

Explanation: 0 (right child of 9) and 1 (left child of 8) are both at row 2, column 0. Node 0 comes before node 1 in that row, so column 0 is [3, 0, 1].

Example 3

Input: tree = []

Output: []