Top View of a Binary Tree

Algorithm Steps

If the tree is empty, return an empty result.
Initialize a queue and enqueue a tuple containing the root node and its horizontal distance (0).
Initialize an empty map (or dictionary) to store the first node encountered at each horizontal distance.
While the queue is not empty, dequeue a tuple (node, hd).
If the horizontal distance hd is not present in the map, record the node's value for that hd.
Enqueue the left child with horizontal distance hd - 1 and the right child with hd + 1 (if they exist).
After processing all nodes, sort the keys of the map and output the corresponding node values as the top view.

Top View of a Binary Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def topView(root):
    if not root:
        return []
    from collections import deque
    queue = deque([(root, 0)])
    hd_map = {}
    while queue:
        node, hd = queue.popleft()
        if hd not in hd_map:
            hd_map[hd] = node.val
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    return [hd_map[hd] for hd in sorted(hd_map)]

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #         1
    #        / \
    #       2   3
    #      / \   \
    #     4   5   6
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))
    print(topView(root))