Top View of a Binary Tree - Iterative - Visualization

Understanding the Problem

The Top View of a binary tree refers to the set of nodes visible when we look at the tree from the top. For each vertical column (based on horizontal distance from the root), we should see only the topmost node — the one that appears first in a top-down traversal.

We’ll solve this using a level-order traversal (BFS) approach, and for each horizontal distance (HD), we record the first node we encounter. This way, we capture the top view from left to right.

Step-by-Step Solution with Example

step 1: Visualize the Tree

Consider the binary tree:

       1
     /       2     3
        /       4 5   6

Here, node 1 is the root. Node 2 is on the left, node 3 is on the right. Node 4 is the right child of 2, and nodes 5 and 6 are the children of 3.

step 2: Define Horizontal Distance

Assign a horizontal distance (HD) to each node:

• Root (1) has HD = 0
• Left child decreases HD by 1
• Right child increases HD by 1

So we get:

• Node 1: HD = 0
• Node 2: HD = -1
• Node 3: HD = +1
• Node 4: HD = 0
• Node 5: HD = 0
• Node 6: HD = +2

step 3: Perform Level-Order Traversal

Use a queue for BFS. Track both node and its HD. Maintain a map where key = HD and value = first node seen at that HD.

Processing in BFS order (top to bottom, left to right):

1. Visit node 1 (HD=0) → not in map → add
2. Visit node 2 (HD=-1) → not in map → add
3. Visit node 3 (HD=1) → not in map → add
4. Visit node 4 (HD=0) → already in map → skip
5. Visit node 5 (HD=0) → already in map → skip
6. Visit node 6 (HD=2) → not in map → add

step 4: Extract and Sort Results

The map now has nodes at each horizontal distance:

• HD = -1 → Node 2
• HD = 0 → Node 1
• HD = 1 → Node 3
• HD = 2 → Node 6

Sort keys: [-1, 0, 1, 2], then print values in that order: [2, 1, 3, 6]

Edge Cases

Empty Tree

If the tree is empty (root = null), then the top view is simply an empty list.

Single Node Tree

If the tree has only one node (the root), then the top view contains just that one node.

Left-Skewed Tree

Each node only has a left child. Every node will have a unique HD (all negative) and will be visible from the top.

Right-Skewed Tree

Each node only has a right child. Each node gets a unique positive HD and will appear in the top view.

Overlapping Nodes at Same HD

In trees where multiple nodes share the same HD, only the first node encountered in level-order traversal is taken for the top view. This ensures higher nodes (closer to root) are prioritized.

Finally

The top view of a binary tree helps us understand its vertical structure from above. By tracking horizontal distances during a BFS traversal, we efficiently extract the topmost visible node at each vertical level. Always sort the HDs before output to ensure left-to-right ordering.

This method ensures correctness for all types of binary trees — from skewed to balanced and general trees with complex structures.

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