Top View of Binary Tree

Medium
1963.

Top View of Binary Tree

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.

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^5
  • 1 <= Node.val <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var topView = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= Node.val <= 10^5

Hints for Top View of Binary Tree

  1. Hint 1

    Give every node a column number: root 0, left child column − 1, right child column + 1.

  2. 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.

  3. 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

  1. Run a breadth-first traversal from the root, carrying each node's column (left child c - 1, right child c + 1).
  2. When a node's column has no entry yet, store the node's value for that column.
  3. Track the smallest and largest column seen (columns are contiguous, from min to max).
  4. 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)