Solve common string/tree/grid interview tasks

Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, return the vertical order traversal of its nodes' values.

For each node at position (row, col), its left child will be at position (row + 1, col - 1) and its right child will be at position (row + 1, col + 1). The root is at (0, 0).

Requirements:

1. If two nodes have the same column and row, the node with the smaller value appears first.
2. If two nodes have the same column and row and the same value, their relative order does not matter (though they should both appear).
3. You must order the columns from the leftmost to the rightmost. Within each column, nodes should be ordered by their row index (top to bottom).

Function Signature:

def verticalTraversal(root: TreeNode) -> List[List[int]]:

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[9],[3,15],[20],[7]] Explanation:

• Column -1: [9]
• Column 0: [3, 15]
• Column 1: [20]
• Column 2: [7]

Example 2:

Input: root = [1,2,3,4,5,6,7] Output: [[4],[2],[1,5,6],[3],[7]]

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 1000
• Time complexity should be better than O(N^2).