Top View of Binary Tree | Level Order Traversal

Problem Statement

Given the root of a binary tree, return the nodes visible when the tree is viewed from the top.

For every horizontal distance (HD), only the first node encountered should be included.

Brute Force Intuition

In an interview, you can explain it like this:

Compute the horizontal distance of every node and store all nodes belonging to the same horizontal distance. Finally, choose the topmost node for each horizontal distance.

This requires storing multiple nodes for every horizontal distance.

Complexity

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Moving Towards the Optimal Approach

Notice that:

BFS

↓

Processes Nodes

Level by Level

The first node encountered for a particular:

Horizontal Distance

will always be the topmost node.

So we only need to store it once.

Pattern Recognition

Whenever you see:

• Top View
• Bottom View
• Vertical Traversal

Think:

Level Order Traversal + Horizontal Distance

Key Observation

Assign every node a:

Horizontal Distance (HD)

Rules:

Root → 0

Left Child → HD - 1

Right Child → HD + 1

If an HD appears for the first time,

store that node.

Ignore all future nodes with the same HD.

Optimal Approach

Step 1

Perform BFS.

Queue stores:

(Node, HD)

Step 2

Maintain:

TreeMap<Integer, Integer>

Key:

Horizontal Distance

Value:

Node Value

Step 3

If HD is not already present:

map.put(hd, node.data);

Step 4

Traverse the TreeMap from left to right.

Optimal Java Solution

class Pair {

    Node node;
    int hd;

    Pair(Node node, int hd) {

        this.node = node;
        this.hd = hd;
    }
}

class Solution {

    static ArrayList<Integer> topView(Node root) {

        ArrayList<Integer> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<Pair> q = new LinkedList<>();

        TreeMap<Integer, Integer> map =
            new TreeMap<>();

        q.offer(new Pair(root, 0));

        while (!q.isEmpty()) {

            Pair curr = q.poll();

            if (!map.containsKey(curr.hd)) {

                map.put(curr.hd,
                        curr.node.data);
            }

            if (curr.node.left != null)

                q.offer(new Pair(
                    curr.node.left,
                    curr.hd - 1));

            if (curr.node.right != null)

                q.offer(new Pair(
                    curr.node.right,
                    curr.hd + 1));
        }

        ans.addAll(map.values());

        return ans;
    }
}

Dry Run

          1
        /   \
       2     3
      / \   / \
     4   5 6   7

Horizontal Distances:

4 → -2

2 → -1

1 → 0

3 → +1

7 → +2

Nodes:

5

6

are ignored because:

HD already occupied

Final Answer:

[4,2,1,3,7]

Why BFS Works?

BFS visits nodes level by level.

The first node encountered at each horizontal distance is always the highest (topmost) node.

Once an HD is recorded,

it should never be replaced.

Complexity Analysis

log N comes from inserting keys into the TreeMap.

Interview One-Liner

Perform a level-order traversal while tracking horizontal distances, and store only the first node encountered for each horizontal distance.

Pattern Learned

BFS

↓

Horizontal Distance

↓

First Node

↓

Top View

Similar Problems

• Top View of Binary Tree
• Bottom View of Binary Tree
• Vertical Order Traversal
• Vertical Sum
• Left View
• Right View

Memory Trick

Think:

Horizontal Distance

↓

Seen Before?

↓

No

↓

Store It

↓

Ignore Future Nodes

Mental Model

Queue

↓

(Node, HD)

↓

First Node at HD

↓

Answer

Whenever you hear:

"Top View of Binary Tree"

your brain should immediately think:

BFS + Horizontal Distance + First Node