#include <iostream>
#include <queue>
#include <map>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int val) : data(val), left(nullptr), right(nullptr) {}
};
void topView(Node* root) {
if (!root) return;
// Map to store first node at each horizontal distance
map<int, int> top_nodes;
// Queue stores pairs of node and its horizontal distance
queue<pair<Node*, int>> q;
q.push({root, 0});
while (!q.empty()) {
auto [node, hd] = q.front();
q.pop();
// If hd not seen before, add node data
if (top_nodes.find(hd) == top_nodes.end()) {
top_nodes[hd] = node->data;
}
if (node->left) q.push({node->left, hd - 1});
if (node->right) q.push({node->right, hd + 1});
}
// Print top view from leftmost to rightmost hd
for (auto& [hd, val] : top_nodes) {
cout << val << " -> ";
}
cout << "null" << endl;
}
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->right = new Node(4);
root->right->right = new Node(5);
topView(root);
return 0;
}Start BFS from root with horizontal distance 0
auto [node, hd] = q.front();
q.pop();
Dequeue current node and its horizontal distance
if (top_nodes.find(hd) == top_nodes.end()) {
top_nodes[hd] = node->data;
}
Add node data if this horizontal distance is seen first time
if (node->left) q.push({node->left, hd - 1});
if (node->right) q.push({node->right, hd + 1});
Add left and right children with updated horizontal distances
for (auto& [hd, val] : top_nodes) {
cout << val << " -> ";
}
cout << "null" << endl;
Print nodes in order from leftmost to rightmost horizontal distance