Top View of Binary Tree

Medium Trees & BST Views Original on GeeksforGeeks

Top View of Binary Tree is a medium trees & bst problem solved with the views pattern. The best approach, bfs with columns (first seen wins), runs in O(n) time and O(n) space. Below are 2 approaches in Java, from dfs tracking depth per column up.

Problem

Return the top view of a binary tree: the nodes you see when looking down from above, ordered from the leftmost column to the rightmost.

Examples

Example 1

Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [4, 2, 1, 3, 7]
Why: 5 and 6 sit under 1 in column 0, so they are hidden.

Example 2

Input: root = [1, 2, null, null, 3, null, 4]
Output: [2, 1, 4]

Constraints

The tree has 1 to 10^5 nodes.
Order the answer from the leftmost column to the rightmost.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
DFS tracking depth per column	`O(n log n)`	`O(n)`
BFS with columns (first seen wins)	`O(n)`	`O(n)`

1DFS tracking depth per column

TimeO(n log n)

SpaceO(n)

DFS with (column, depth). For each column keep the node with the smallest depth; ties keep the one visited first.

map column → (depth, value); replace only when the depth is smaller.
Read the map in column order.

Java

class Solution {
    public ArrayList<Integer> topView(TreeNode root) {
        TreeMap<Integer, int[]> best = new TreeMap<>();
        dfs(root, 0, 0, best);
        ArrayList<Integer> out = new ArrayList<>();
        for (int[] v : best.values()) out.add(v[1]);
        return out;
    }

    private void dfs(TreeNode n, int col, int depth, TreeMap<Integer, int[]> best) {
        if (n == null) return;
        int[] cur = best.get(col);
        if (cur == null || depth < cur[0]) best.put(col, new int[] { depth, n.val });
        dfs(n.left, col - 1, depth + 1, best);
        dfs(n.right, col + 1, depth + 1, best);
    }
}

2BFS with columns (first seen wins)

TimeO(n)

SpaceO(n)

Level order visits shallower nodes first, so the first node recorded for each column is the one visible from above. Track min and max column to output in order without sorting.

Queue of (node, col); map col → value, putIfAbsent.
Track min and max col; output map[min..max].

Java

class Solution {
    public ArrayList<Integer> topView(TreeNode root) {
        Map<Integer, Integer> first = new HashMap<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        Queue<Integer> cols = new ArrayDeque<>();
        q.add(root); cols.add(0);
        int min = 0, max = 0;
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            int c = cols.poll();
            first.putIfAbsent(c, n.val);
            min = Math.min(min, c); max = Math.max(max, c);
            if (n.left != null) { q.add(n.left); cols.add(c - 1); }
            if (n.right != null) { q.add(n.right); cols.add(c + 1); }
        }
        ArrayList<Integer> out = new ArrayList<>();
        for (int c = min; c <= max; c++) out.add(first.get(c));
        return out;
    }
}

Edge cases to test

Nodes deep in the tree reaching a new column
Two nodes in one column at the same depth (take the leftmost one reached by BFS)

Hints

Hint 1

Give the root column 0, left children column - 1, right children column + 1. The top view is the first node seen in each column in level order.

FAQ

What is the best time complexity for Top View of Binary Tree?

BFS with columns (first seen wins) runs in O(n) time and O(n) extra space.

Which pattern does Top View of Binary Tree use?

It is a trees & bst problem that uses the views pattern. Other problems with the same pattern: Bottom View of Binary Tree, Left View of Binary Tree, Binary Tree Right Side View.

Is there a brute force solution for Top View of Binary Tree?

Yes. DFS tracking depth per column takes O(n log n) time and O(n) space. DFS with (column, depth).

Which edge cases should I test for Top View of Binary Tree?

Nodes deep in the tree reaching a new column; Two nodes in one column at the same depth (take the leftmost one reached by BFS).