Vertical order traversal
Place every node of a binary tree on a grid. The root is at column 0, row 0. A left child sits one column to the left of its parent, a right child one column to the right, and both sit one row lower.
Your function gets the tree's root. Return the 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 nodes share a column and a row, list them in the order a level by level walk meets them, left to right; never sort them by value. An empty tree (root is None) gives [].
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [5, 2, 7, None, 4, 6]Output[[2], [5, 4, 6], [7]]2 is in column -1 and 7 in column 1. The 4 (right child of 2) and the 6 (left child of 7) both land in column 0, row 2, below the 5. A level by level walk meets the 4 first, because its parent 2 is left of the 7.
root = [1, 2, 3, None, 4, None, None, None, 5]Output[[2], [1, 4], [3, 5]]5 is the right child of 4, so it lands in column 1 at row 3. 3 is in column 1 at row 1, so 3 comes first, even though 5 hangs under the left half of the tree.
root = []Output[]No nodes, no columns.
0 ≤ number of nodes ≤ 1.3 × 105
-104 ≤ node value ≤ 104
The tree is at most 500 levels deep, so a recursive solution fits under plain Python's default of about 1,000 nested calls.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.