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
| Metric | Complexity |
|---|---|
| Time Complexity | O(N log N) |
| Space Complexity | O(N) |
log Ncomes from inserting keys into theTreeMap.
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