Top-Down View

Top View of a Binary Tree

Imagine looking at the tree from above. You only see the first node at each vertical position. BFS guarantees the topmost node is discovered first — the map keeps only that one.

Green = selected as top view

Red dashed = blocked (vertical already taken)

x = vertical position (left = -1, right = +1)

top_view.cpp

1map<int, int> mpp;2queue<pair<Node*, int>> q;3q.push({root, 0});4while (!q.empty()) {5 auto it = q.front(); q.pop();6 Node* node = it.first;7 int line = it.second;8 if (mpp.find(line) == mpp.end()) {9 mpp[line] = node->data;10 }11 if (node->left) q.push({node->left, line - 1});12 if (node->right) q.push({node->right, line + 1});13}14for (auto it : mpp) ans.push_back(it.second);

Tree with vertical (x) coordinates

BFS Queue (node, vertical)

(empty)

map mpp (vertical → top node)

(empty — first node at each vertical will be stored)

Top View (left to right)

(empty)

Step 1 / 1

What's Happening Now

We start by pushing root 1 with vertical x=0 into the queue. The map is empty. Press Next ▶ to step through the BFS and see which nodes make it into the top view.

Key Ideas — Why BFS + "First Seen" = Top View

01

BFS goes top-down, so first = topmost

BFS processes nodes level by level — all of level 0 before any of level 1. So the first time we encounter a vertical x, the node is at the shallowest depth for that column. That's the topmost node — the one visible from above.

02

The map check: first-come, first-served

if (mpp.find(line) == mpp.end()) checks if this vertical is empty. If yes, store the node. If not, skip — someone shallower already claimed this column. This is the entire filtering logic. No comparisons, no depth tracking.

03

Why not DFS?

DFS would also work if you track depth and keep the minimum-depth node per vertical. But BFS is cleaner — the first node discovered at each vertical is automatically the topmost. No depth comparison needed. The queue's FIFO order does the work.

04

Same as vertical order, but "first only"

Compare with the vertical-order visualizer: that one collects all nodes at each vertical into a list. This one keeps only the first — a single int per vertical. The difference is one line: if (mpp.find(line) == mpp.end()) vs always inserting.