https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree

First of all, I want to mention, that problem statement is not clear at all, I need to go to comments to understand, what order they expect us to return nodes in levels. So, we have X coordinate and Y coordinate, we need to group them by X coordinate. If we have the same X coordinate, we need to check:

  1. First put nodes with higher Y coordinates, that ones, which are close to root
  2. If two nodes have the same Y coordinate also, we need to put small values before big values.

Let us define dic, where we create our vertical layers, and self.min_l and self.max_l be minimal and maximal numbers of vertical layers. Let us start to traverse our graph, using dfs, with parameters:

  1. root is current node we are in now
  2. lvl_h is horizontal coordinate, that is X
  3. lvl_v is vertical coordinate, that is -Y: note, that I increase my Y coordinate as I go down, it is simpler to deal in this way.

Inside dfs we do the following steps:

  1. Update self.min_l and self.max_l.
  2. Add lvl_v and root.val pair to our dictionary. We need to add pair to sort it after.
  3. Finally, visit left and right children if it is possible.

In the end, we need to sort each level, and add it to final list of lists.

Complexity: Usual dfs traversal will take O(n) time. However we need to sort each level, before we give final result. Let us have w_1, ..., w_h nodes on each layer. then we need to do w_1 log w_1 + ... + w_h log w_h < n * log W operations, where W is width of the biggest layer. So, complexity is O(n log W), which potentially can be O(n log n), because the widest level can have upto n/2 nodes. Space complexity is O(n).

class Solution:
    def verticalTraversal(self, root):
        dic = defaultdict(list)
        self.min_l, self.max_l = float("inf"), -float("inf")
        def dfs(root, lvl_h, lvl_v):
            self.min_l = min(lvl_h, self.min_l)
            self.max_l = max(lvl_h, self.max_l)
            dic[lvl_h].append((lvl_v, root.val))
            if root.left:  dfs(root.left,  lvl_h-1, lvl_v+1)
            if root.right: dfs(root.right, lvl_h+1, lvl_v+1)
        
        dfs(root, 0, 0)
        out = []
        for i in range(self.min_l, self.max_l + 1):
            out += [[j for i,j in sorted(dic[i])]]
        return out

If you like the solution, you can upvote it on leetcode discussion section: Problem 0987