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 12 / \3 2 34 / \ \5 4 5 6Assign 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
- Use a queue of
(node, hd)pairs. Start with(root, 0). - Keep a sorted map from hd to value.
- 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.
- Push
(left, hd - 1)and(right, hd + 1). - 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
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).
The queue and the map hold up to O(n) entries.