On this page

Top View of Binary Tree

Given a binary tree, return its top view: the nodes that are visible when you look at the tree from above, listed from the leftmost to the rightmost horizontal position.

If two nodes sit at the same horizontal position, only the higher one (closer to the root) is visible.

Intuition

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

Assign each node a horizontal distance (hd): the root is 0, a left child is hd - 1, a right child is hd + 1. Here node 4 has hd -2, node 2 has -1, nodes 1 and 5 have 0, node 3 has 1, node 6 has 2.

Seen from above, each hd shows only the first node you meet going top to bottom. Top view is 4, 2, 1, 3, 6 (at hd 0, node 1 hides node 5).

So we need the first node per hd in top-down order. That is exactly what level order traversal gives us: it visits shallower nodes before deeper ones.

Approach: BFS with Horizontal Distance

  1. Use a queue of (node, hd) pairs. Start with (root, 0).
  2. Keep a sorted map from hd to value.
  3. Pop a pair. If this hd is not in the map yet, store the node's value. Otherwise ignore it, because a higher node already took that spot.
  4. Push (left, hd - 1) and (right, hd + 1).
  5. At the end, read the map in increasing hd order.

DFS would be wrong here unless you also track depth, since it can reach a deeper node at the same hd before a shallower one. BFS avoids that by going level by level.

Code

class Solution {
public:
vector<int> topView(Node* root) {
vector<int> ans;
if (root == nullptr) return ans;
map<int, int> top;
queue<pair<Node*, int>> q;
q.push({root, 0});
while (!q.empty()) {
Node* node = q.front().first;
int hd = q.front().second;
q.pop();
if (top.find(hd) == top.end()) top[hd] = node->data;
if (node->left != nullptr) q.push({node->left, hd - 1});
if (node->right != nullptr) q.push({node->right, hd + 1});
}
for (auto& entry : top) ans.push_back(entry.second);
return ans;
}
};

Complexity

Time: O(n log n)

BFS visits each node once. Using a sorted map adds a log factor (it is O(n) with a hash map plus tracking the min and max hd).

Space: O(n)

The queue and the map hold up to O(n) entries.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"I give each node a horizontal distance: root is zero, left child minus one, right child plus one. The top view is the first node I meet at each distance when going from the top down, so I do a level order traversal, because BFS reaches shallower nodes first. I keep a queue of node and distance pairs and a sorted map from distance to value. When I pop a node, I store its value only if that distance is not already in the map. Then I push the children with their distances. At the end I read the map from the smallest distance to the largest. DFS would need extra depth tracking, which is why BFS is the right tool. Time is O of n log n with a sorted map, and space is O of n."
Next TopicBottom View of Binary Tree