Log inSign up
mediumgeeksforgeeksNot Started

Top View of Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on geeksforgeeks
Lesson

Problem Statement

Given a binary tree, print the top view from left to right.

A node is included in top view if it is the highest (uppermost) node at its horizontal distance. If multiple nodes exist at the same horizontal distance, only the one with the smallest depth (first visited in BFS) is included.

Example 1 · Example 1: Tree with Multiple Columns:

Input: root = [1, 2, 3, 4, 5, 6, 7] Tree: 1 / \ 2 3 / \ / \ 4 5 6 7
Output: [4, 2, 1, 3, 7]
Explanation: Columns: HD -2: 4; HD -1: 2; HD 0: 1; HD 1: 3; HD 2: 7 (nodes 5 and 6 are blocked by 1).

Example 2 · Example 2: 3-Node Tree:

Input: root = [1, 2, 3] Tree: 1 / \ 2 3
Output: [2, 1, 3]
Explanation: HD -1 is 2, HD 0 is 1, HD 1 is 3.

Constraints:

  • 1 <= Number of nodes <= 105
  • 1 <= Data of a node <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply horizontal distance coordinate system.
  • Understand why BFS naturally guarantees first-seen is top-most.
  • Optimize output with minHD and maxHD bounds.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • View from the top.
  • Horizontal distance projection.
  • First visible node in each column.

Algorithmic Decision Tree:

  • if (!map.count(hd)) map[hd] = node.val.
  • push left with hd - 1, right with hd + 1.

Connected Patterns:

Bottom View of Binary TreeVertical Order TraversalBinary Tree Right Side View

1. DFS with (Depth, HD) Tracking

Intuition

Traverse tree with DFS. Store (val, depth) in map. If HD not in map or depth < map[hd].depth, update. Sort keys at end.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Helper dfs(node, hd, depth, map).
  2. Step 2: If hd not in map or depth < map[hd].depth: map[hd] = (node.val, depth).
  3. Step 3: dfs(left, hd - 1, depth + 1); dfs(right, hd + 1, depth + 1).
  4. Step 4: Sort map keys and return values.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void dfs(TreeNode* node, int hd, int depth, map<int, pair<int, int>>& m) {
10 if (!node) return;
11 if (!m.count(hd) || depth < m[hd].second) {
12 m[hd] = {node->val, depth};
13 }
14 dfs(node->left, hd - 1, depth + 1, m);
15 dfs(node->right, hd + 1, depth + 1, m);
16 }
17 vector<int> topView(TreeNode* root) {
18 map<int, pair<int, int>> m;
19 dfs(root, 0, 0, m);
20 vector<int> res;
21 for (auto& p : m) res.push_back(p.second.first);
22 return res;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n log n) — DFS is O(n); sorting map keys takes O(w log w).
  • Space complexity: O(n) — Map stores entries for up to n nodes.

2. BFS with Ordered Map

Intuition

Level order queue. Insert node.val into tree map if hd not present. Iterate tree map values.

When to apply: Standard BFS approach.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Queue stores pairs (node, hd). Push (root, 0).
  3. Step 3: Pop (node, hd). If hd not in map, map[hd] = node.val.
  4. Step 4: Push left with hd - 1, right with hd + 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> topView(TreeNode* root) {
10 if (!root) return {};
11 map<int, int> m;
12 queue<pair<TreeNode*, int>> q;
13 q.push({root, 0});
14 while (!q.empty()) {
15 auto [node, hd] = q.front(); q.pop();
16 if (!m.count(hd)) m[hd] = node->val;
17 if (node->left) q.push({node->left, hd - 1});
18 if (node->right) q.push({node->right, hd + 1});
19 }
20 vector<int> res;
21 for (auto& p : m) res.push_back(p.second);
22 return res;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n log w) — Ordered map insertion takes O(log w).
  • Space complexity: O(n) — Queue and map store O(n) nodes.

3. BFS with Dynamic Min/Max Bounds (Strict O(n))

Intuition

Unordered hash map with first-seen check. Track minHD and maxHD dynamically. Loop from minHD to maxHD to collect answer in strict linear time.

When to apply: Optimal gold-standard solution for strict O(n) linear performance.

Algorithm

  1. Step 1: If root == null return [].
  2. Step 2: Initialize minHD = 0, maxHD = 0, unordered_map topMap.
  3. Step 3: Queue stores pairs (node, hd). Push (root, 0).
  4. Step 4: Pop (node, hd). If hd not in topMap: topMap[hd] = node.val; minHD = min(minHD, hd); maxHD = max(maxHD, hd).
  5. Step 5: Push children. Iterate hd from minHD to maxHD and collect.

Top View BFS Trace for root = [1, 2, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Process root 1 (HD 0)
Visual state
Values and pointers at this exact step
tree
Root
1 (HD 0)
L
2
R
3

Node order shown; add connections to display explicit tree edges.

hd: 0: 1
Check / comparison
map[0] = 1
Decision / next transition
Record root 1.
Why this step matters

Step 1: Process root 1 (HD 0). map[0] not present -> map[0] = 1. Enqueue left (2, HD -1) and right (3, HD 1).

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> topView(TreeNode* root) {
10 if (!root) return {};
11 unordered_map<int, int> m;
12 queue<pair<TreeNode*, int>> q;
13 q.push({root, 0});
14 int minHd = 0, maxHd = 0;
15 while (!q.empty()) {
16 auto [node, hd] = q.front(); q.pop();
17 if (!m.count(hd)) {
18 m[hd] = node->val;
19 minHd = min(minHd, hd);
20 maxHd = max(maxHd, hd);
21 }
22 if (node->left) q.push({node->left, hd - 1});
23 if (node->right) q.push({node->right, hd + 1});
24 }
25 vector<int> res;
26 for (int hd = minHd; hd <= maxHd; ++hd) {
27 res.push_back(m[hd]);
28 }
29 return res;
30 }
31};
32
33int main() {
34 // Sample driver execution
35 cout << "Execution completed successfully." << endl;
36 return 0;
37}
38

Time & Space Complexity

  • Time complexity: O(n) — All operations O(1) per node; bounds loop runs in O(w) <= O(n).
  • Space complexity: O(n) — Queue and hash map hold O(n) elements.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS with Depth TrackingO(n log n)O(n)Recursively check depth < storedDepth.Depth tracking and key sorting.
2.BFS with Ordered MapO(n log w)O(n)Queue BFS with tree map.Tree map.
3.BFS with Min/Max BoundsOptimalO(n)O(n)Unordered hash map with min/max bounds tracking.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node tree: returns [root.val].
  • Skewed tree: all nodes appear in top view.
  • Nodes overlapping in column: only uppermost is visible.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast Top View with Bottom View: Top View uses if (!map.count(hd)) while Bottom View overwrites unconditionally.
  2. Explain why BFS is vastly superior to DFS here: DFS requires comparing depths, whereas BFS naturally guarantees first occurrence is top-most.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does BFS guarantee that the first node encountered at any horizontal distance hd is the top-most visible node?

Back to DSA Sheet