Problem statement

https://binarysearch.com/problems/Top-View-of-a-Tree/

Solution

Variation to Leetcode 0987. Vertical Order Traversal of a Binary Tree, if you do not know it in advance, it is difficult to understand what is asked in this problem.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(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 += [min(dic[i])[1]]
        return out