Top View of Binary Tree — Solution in Python, Java & C++
Top View of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Top View of Binary Tree is a medium coding problem on hash table, breadth-first search and trees, asked in Amazon, Samsung and Walmart interviews.
- Difficulty: Medium
- Topics: Hash Table, Breadth-First Search, Trees
- Asked at: Amazon, Samsung, Walmart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return its top view: the values you would see looking down on the tree from above, listed from the leftmost column to the rightmost.
The root is in column 0; a node's left child is one column to the left (-1) and its right child one column to the right (+1). For each column, the visible node is the one closest to the root (smallest depth); if two nodes of a column are at the same depth, the one that comes first in a left-to-right level-order traversal is visible.
Example 1
Input: root = [1,2,3,4,5,6,7]
Output: [4,2,1,3,7]
Explanation: Columns −2..2 are first reached by 4, 2, 1, 3 and 7. 5 and 6 share column 0 with 1 and sit below it.
Example 2
Input: root = [10,20,30,40,60,90,100]
Output: [40,20,10,30,100]
Explanation: Seen from above: 40, 20, 10, 30, 100.
Example 3
Input: root = [1,2,null,null,3,null,4,null,5]
Output: [2,1,4,5]
Explanation: The chain bends back right: 3 lands in column 0, hidden under the root, while 4 and 5 open columns 1 and 2.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^5
Hints for Top View of Binary Tree
Hint 1
Give every node a column number: root 0, left child column − 1, right child column + 1.
Hint 2
The visible node of a column is the first one met when you go from the top down — that is exactly the order of a breadth-first (level-order) traversal.
Hint 3
Run a BFS carrying each node's column; record a node only if its column has not been seen yet. Then output the columns from the smallest to the largest.
How to solve Top View of Binary Tree
A level-order traversal meets nodes by increasing depth, left to right within a depth — the visibility rule exactly. Recording the first node per column during BFS gives the top view.
Approach
- Run a breadth-first traversal from the root, carrying each node's column (left child
c - 1, right childc + 1). - When a node's column has no entry yet, store the node's value for that column.
- Track the smallest and largest column seen (columns are contiguous, from
mintomax). - Return the stored values for the columns
min, min + 1, …, max.
Why it works
BFS visits all nodes of depth d before any of depth d + 1, and within a depth from left to right, so the first node recorded for a column is its shallowest, leftmost-in-level-order node — the one the view shows. Every column between the extremes is occupied, because the path from the root to an extreme node passes through every column in between.
Complexity
- Time —
O(n) with an array or hash map indexed by column (O(n log n) with a sorted map) - Space —
O(n)
Pitfalls
- A depth-first traversal visits a deep left-subtree node before a shallow right-subtree node of the same column; without tracking depth it records the wrong one.
- Columns can be negative — offset them by the node count when indexing an array.
Reference solution
Python
from typing import List, Optional
def topView(root: Optional[TreeNode]) -> List[int]:
if root is None:
return []
first = {}
queue = [(root, 0)]
head = 0
while head < len(queue):
node, col = queue[head]
head += 1
if col not in first:
first[col] = node.val
if node.left:
queue.append((node.left, col - 1))
if node.right:
queue.append((node.right, col + 1))
return [first[c] for c in range(min(first), max(first) + 1)]Java
public static int[] topView(TreeNode root) {
if (root == null) return new int[0];
Map<Integer, Integer> first = new HashMap<>();
List<TreeNode> nodes = new ArrayList<>();
List<Integer> cols = new ArrayList<>();
nodes.add(root);
cols.add(0);
int lo = 0, hi = 0;
for (int h = 0; h < nodes.size(); h++) {
TreeNode node = nodes.get(h);
int col = cols.get(h);
if (!first.containsKey(col)) first.put(col, node.val);
lo = Math.min(lo, col);
hi = Math.max(hi, col);
if (node.left != null) { nodes.add(node.left); cols.add(col - 1); }
if (node.right != null) { nodes.add(node.right); cols.add(col + 1); }
}
int[] out = new int[hi - lo + 1];
for (int c = lo; c <= hi; c++) out[c - lo] = first.get(c);
return out;
}C++
vector<int> topView(TreeNode* root) {
if (!root) return {};
map<int, int> first;
vector<pair<TreeNode*, int>> q = {{root, 0}};
for (size_t h = 0; h < q.size(); h++) {
TreeNode* node = q[h].first;
int col = q[h].second;
if (!first.count(col)) first[col] = node->val;
if (node->left) q.push_back({node->left, col - 1});
if (node->right) q.push_back({node->right, col + 1});
}
vector<int> out;
for (auto& kv : first) out.push_back(kv.second);
return out;
}JavaScript
var topView = function(root) {
if (root === null) return [];
var first = {}, lo = 0, hi = 0;
var nodes = [root], cols = [0], head = 0;
while (head < nodes.length) {
var node = nodes[head], col = cols[head];
head++;
if (!(col in first)) first[col] = node.val;
if (col < lo) lo = col;
if (col > hi) hi = col;
if (node.left !== null) { nodes.push(node.left); cols.push(col - 1); }
if (node.right !== null) { nodes.push(node.right); cols.push(col + 1); }
}
var out = [];
for (var c = lo; c <= hi; c++) out.push(first[c]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Breadth-First Search (BFS)