Problem statement

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

Solution

Almost the same as Problem 0987. Vertical Order Traversal of a Binary Tree. The difference here is the order in which we need to give nodes if they have the same coordinates. For each vertical layer we need to sort them by horizontal coordinate and about values, keep them like this. Note, that in Problem 0987, we sorted by key = lambda x: (x[0], x[1]), and we can not do it here, if we have the same x[0], we need to keep order from left to right (as it is already, because we consturcted it in this way), not from smallest to biggest

Complexity

It can be estimated similarly to 0987 as $O(n\log w)$.

Code

class Solution:
    def verticalOrder(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)
        
        if not root: return []
        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], key=lambda x:x[0])]]
        return out

Remark

There is also bfs solution, where we can avoid sorting with $O(n)$ time complexity.