Practice › Trees
Top View of a Binary Tree
Medium · Trees · Asked at Amazon, Microsoft, Walmart, Paytm
Give the root column 0; a left child is in column − 1 of its parent, a right child in column + 1. The top view shows, for every column from left to right, the node of that column that comes first in level order (left to right within a level).
Input
First line: k. Second line: k values — the tree in level order, -1 means no node.
Output
The top view from the leftmost column to the rightmost, space-separated.
Constraints
- 1 ≤ number of nodes ≤ 10^4
BFS carrying the column number; record a node only if its column has not been seen yet.
Example 1
Input
7 1 2 3 4 5 6 7
Output
4 2 1 3 7
Example 2
Input
11 1 2 3 -1 4 -1 -1 -1 5 -1 6
Output
2 1 3 6
Hints
- Track a column for every node: left child = column − 1, right child = column + 1.
- Traverse level by level (BFS); the first node you meet in a column is the one seen from the top.
Approach
BFS with (node, column) pairs. Keep a map column → value and insert only when the column is new — BFS order guarantees that the first node seen in a column is the highest one (and the leftmost among equals). Output the map in increasing column order. A DFS would be wrong here: it can reach a deep node in a column before a shallower one.
Complexity: O(n log n) time with an ordered map · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
int main() {
Node *root = readTree();
map<int, long long> first;
queue<pair<Node *, int>> q;
q.push({root, 0});
while (!q.empty()) {
Node *n = q.front().first;
int c = q.front().second;
q.pop();
if (!first.count(c)) first[c] = n->val;
if (n->left) q.push({n->left, c - 1});
if (n->right) q.push({n->right, c + 1});
}
bool sp = false;
for (auto &e : first) cout << (sp ? " " : "") << e.second, sp = true;
cout << "\n";
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def build_tree(v):
"""Build a tree from level order where -1 means "no node"."""
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < len(v):
cur = q.popleft()
if i < len(v) and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < len(v) and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
data = list(map(int, sys.stdin.read().split()))
k = data[0]
root = build_tree(data[1 : 1 + k])
rest = data[1 + k :]
first, q = {}, deque([(root, 0)])
while q:
n, c = q.popleft()
first.setdefault(c, n.val)
if n.left:
q.append((n.left, c - 1))
if n.right:
q.append((n.right, c + 1))
print(*[first[c] for c in sorted(first)])Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
public static void main(String[] args) {
Node root = readTree(new Scanner(System.in));
TreeMap<Integer, Long> first = new TreeMap<>();
ArrayDeque<Object[]> q = new ArrayDeque<>();
q.add(new Object[] {root, 0});
while (!q.isEmpty()) {
Object[] t = q.poll();
Node n = (Node) t[0];
int c = (Integer) t[1];
first.putIfAbsent(c, n.val);
if (n.left != null) q.add(new Object[] {n.left, c - 1});
if (n.right != null) q.add(new Object[] {n.right, c + 1});
}
StringBuilder sb = new StringBuilder();
for (long v : first.values()) sb.append(sb.length() > 0 ? " " : "").append(v);
System.out.println(sb);
}
}Solve Top View of a Binary Tree online · All practice problems