987. Vertical Order Traversal of a Binary Tree

This is similar to LC 314, but while requiring sorting. Thus, it’s ok to use either DFS or BFS since they both have the same complexity in the end.

from sortedcontainers import SortedDict
 
class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        nodes = SortedDict()
 
        def traverse(node, row, col):
            if not node:
                return
            if col not in nodes:
                nodes[col] = []
            nodes[col].append((row, node.val))
            traverse(node.left, row + 1, col - 1)
            traverse(node.right, row + 1, col + 1)
        
        traverse(root, 0, 0)
 
        for val in nodes.values():
            val.sort()
 
        return [[node[1] for node in node_list] for level, node_list in nodes.items()]