☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Top View of BT

Medium TUF ID 124 A2ZSDE

Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree. Imagine looking down at the tree from directly above. Return the values of the nodes you can see, ordered from the leftmost vertical line to the rightmost.

To make “vertical line” precise, give every node a column: the root is in column 0, a left child is one column to the left of its parent (col - 1), and a right child is one column to the right (col + 1). In each column, the node you see from above is the one closest to the root (smallest depth). If two nodes share both the column and the depth, the one that comes first in level order (the left one) is the visible one. That is the convention used by the GeeksforGeeks version of this problem.

Constraints: up to 10^5 nodes; node values are arbitrary integers and may repeat. Return an empty list for an empty tree.

Example 1

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

answer = [4, 2, 1, 3, 7]

5 and 6 both fall in column 0, directly under the root, so the root hides them.

Example 2

     1
   /   \
  2     3
   \
    4
     \
      5
       \
        6

answer = [2, 1, 3, 6]

Column -1 holds only 2. Column 0 holds 1 and 4; 1 is on top. Column 1 holds 3 (depth 1) and 5 (depth 3); 3 is on top. Column 2 holds only 6, which is visible even though it is the deepest node in the tree.

Approach 1: DFS that remembers depth

Intuition. “Visible from above” simply means “smallest depth in its column”. So we need, for every column, the shallowest node. Any traversal can find that, as long as each node knows its column and its depth: whenever we reach a column with a node that is strictly shallower than the best one recorded so far, we replace it.

The order of a depth-first traversal is not by depth, which is exactly why the depth must be stored. In Example 2 a preorder walk reaches 5 (column 1, depth 3) before it reaches 3 (column 1, depth 1). A naive “first visitor wins” rule would wrongly report 5.

What about two nodes with the same column and the same depth? Preorder with the left child first visits the nodes of one depth from left to right. Take any two such nodes: their lowest common ancestor has one of them in its left subtree and the other in its right subtree, and preorder finishes the whole left subtree before it enters the right. So keeping the first node on a tie (a strict < comparison) gives the left one, which matches the convention.

A TreeMap keyed by column keeps the columns sorted, so reading its values gives the answer from left to right.

Algorithm.

  1. Walk the tree recursively, passing col and depth.
  2. At each node, look up the column. If it is new, or the stored depth is larger than the current depth, store {depth, value}.
  3. Recurse into the left child with col - 1 and the right child with col + 1, both with depth + 1.
  4. Read the stored values in column order.
static List<Integer> dfsWithDepth(TreeNode root) {
    TreeMap<Integer, int[]> best = new TreeMap<>();          // column -> {depth, value}
    dfs(root, 0, 0, best);
    List<Integer> ans = new ArrayList<>();
    for (int[] dv : best.values()) ans.add(dv[1]);
    return ans;
}

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

Complexity. Time O(n log n): each of the n nodes does a TreeMap lookup and maybe an insert, each O(log w) where w is the number of columns. Space O(n) for the map plus O(h) recursion stack, where h is the height.

Approach 2: BFS with a sorted map

Intuition. A level-order traversal (BFS) visits nodes in order of depth, and within one depth from left to right. That ordering is exactly the visibility rule. The first node to arrive at a column is therefore the shallowest one, and among equally shallow nodes it is the leftmost. So we no longer need to store depths at all: putIfAbsent keeps the first arrival and ignores everyone after it.

The queue has to carry the column along with the node. Two parallel queues (one of nodes, one of columns) keep the code free of a pair class; they are always pushed and popped together, so they stay in step.

Algorithm.

  1. If the tree is empty, return an empty list.
  2. Push (root, 0).
  3. Pop (node, col). Call putIfAbsent(col, node.val).
  4. Push the left child with col - 1 and the right child with col + 1 when they exist.
  5. When the queue is empty, return the map’s values in column order.
static List<Integer> bfsTreeMap(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    TreeMap<Integer, Integer> top = new TreeMap<>();         // column -> value
    Queue<TreeNode> nodes = new ArrayDeque<>();
    Queue<Integer> cols = new ArrayDeque<>();
    nodes.add(root);
    cols.add(0);
    while (!nodes.isEmpty()) {
        TreeNode node = nodes.poll();
        int col = cols.poll();
        top.putIfAbsent(col, node.val);                       // only the first arrival counts
        if (node.left != null) { nodes.add(node.left); cols.add(col - 1); }
        if (node.right != null) { nodes.add(node.right); cols.add(col + 1); }
    }
    ans.addAll(top.values());
    return ans;
}

Complexity. Time O(n log n) because of the TreeMap. Space O(n) for the map and the queues.

Approach 3: Optimal, BFS with a HashMap and the column range

Intuition. The sorted map does only one job: it lets us list the columns from left to right at the end. We can get that for free. Columns form a contiguous range. Every step from parent to child changes the column by exactly one, so the path from the root (column 0) to a node in column c passes through every column between 0 and c. If the leftmost column is minCol and the rightmost is maxCol, every column in between is occupied.

So we track minCol and maxCol while doing the same BFS as before, store the first arrival per column in a plain HashMap, and at the end loop c from minCol to maxCol. Every get(c) is guaranteed to find a value.

Algorithm.

  1. If the tree is empty, return an empty list.
  2. BFS over (node, col) pairs, starting from (root, 0).
  3. For each popped pair: putIfAbsent(col, node.val) and update minCol and maxCol.
  4. After the BFS, append top.get(c) for c = minCol .. maxCol.
static List<Integer> optimal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Map<Integer, Integer> top = new HashMap<>();
    int minCol = 0, maxCol = 0;
    Queue<TreeNode> nodes = new ArrayDeque<>();
    Queue<Integer> cols = new ArrayDeque<>();
    nodes.add(root);
    cols.add(0);
    while (!nodes.isEmpty()) {
        TreeNode node = nodes.poll();
        int col = cols.poll();
        top.putIfAbsent(col, node.val);
        minCol = Math.min(minCol, col);
        maxCol = Math.max(maxCol, 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); }
    }
    for (int c = minCol; c <= maxCol; c++) ans.add(top.get(c));   // columns are contiguous, so none is missing
    return ans;
}

Dry run on Example 2. BFS pops nodes in this order:

popped col stored? map after range
1 0 yes {0:1} 0..0
2 -1 yes {-1:2, 0:1} -1..0
3 1 yes {-1:2, 0:1, 1:3} -1..1
4 0 no, column taken unchanged -1..1
5 1 no, column taken unchanged -1..1
6 2 yes {-1:2, 0:1, 1:3, 2:6} -1..2

Reading columns -1 to 2 gives [2, 1, 3, 6].

Complexity. Time O(n): every node is pushed and popped once and each hash operation is O(1) on average; the final loop runs over at most n columns. Space O(n) for the map and the queue.

Edge cases and pitfalls