Top View of Binary Tree

def topView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the shallowest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first in level order.
        if col not in best or depth < best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [top[col] for col in range(min(top), max(top) + 1)]