Top View of a tree

The problem, simply

You get a binary tree. Look at it from straight above. Some nodes are hidden because another node sits right above them. Write down the nodes you can see, from the leftmost to the rightmost.

To know who is above whom, give each node a column number. The root is in column 0. A left child is one column to the left of its parent (subtract 1). A right child is one column to the right (add 1). In each column, you see only the highest node, the one closest to the root.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk the whole tree any way you like, for example going down with recursion, and carry both the column and the depth. For each column, keep the node with the smallest depth. A sorted map keeps the columns in order from left to right.

1. Visit each node with its column c and depth d.
2. If column c is empty, or the stored depth is bigger than d, store this node.
3. At the end, read the sorted map from the smallest column to the biggest.

import java.util.*;

class Solution {
    // column -> {value, depth}
    private TreeMap<Integer, int[]> best = new TreeMap<>();

    public List<Integer> topView(TreeNode root) {
        best.clear();
        walk(root, 0, 0);
        List<Integer> out = new ArrayList<>();
        for (int[] cell : best.values()) out.add(cell[0]);
        return out;
    }

    private void walk(TreeNode node, int col, int depth) {
        if (node == null) return;
        int[] cell = best.get(col);
        if (cell == null || depth < cell[1]) {          // higher than what we had
            best.put(col, new int[]{node.val, depth});
        }
        walk(node.left, col - 1, depth + 1);
        walk(node.right, col + 1, depth + 1);
    }
}

How long it takes: each node does one sorted map step, O(log n) each, so O(n log n). Extra room: the map and the call stack, O(n).

Way 2: the clever way

Visit the tree floor by floor with a waiting line (a queue), top floor first. Then the first node that shows up in a column is the highest one, so you never need to compare depths. Instead of a sorted map, remember the smallest and biggest column you saw, and read a plain hash map from smallest to biggest at the end.

1. Put (root, 0) in the line.
2. Take the front (node, c). If column c has nobody yet, store node for c.
3. Update the leftmost and rightmost column.
4. Add (left, c - 1) and (right, c + 1) to the back.
5. When the line is empty, read columns from leftmost to rightmost.

import java.util.*;

class Solution {
    public List<Integer> topView(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        Map<Integer, Integer> first = new HashMap<>();   // column -> first value seen
        Deque<TreeNode> line = new ArrayDeque<>();
        Deque<Integer> cols = new ArrayDeque<>();         // column of each node in line
        line.add(root);
        cols.add(0);
        int lo = 0, hi = 0;
        while (!line.isEmpty()) {
            TreeNode node = line.poll();
            int c = cols.poll();
            first.putIfAbsent(c, node.val);               // only the first one counts
            lo = Math.min(lo, c);
            hi = Math.max(hi, c);
            if (node.left != null) { line.add(node.left); cols.add(c - 1); }
            if (node.right != null) { line.add(node.right); cols.add(c + 1); }
        }
        for (int c = lo; c <= hi; c++) out.add(first.get(c));
        return out;
    }
}

How long it takes: every node joins and leaves the line once, and hash map steps are O(1) on average, so O(n). Extra room: the line and the map, O(n).

Columns never skip a number, because each child moves exactly one column, so every column from lo to hi has a node.

Watch out for

• Two nodes in the same column and the same floor: the usual rule keeps the left one, which is the one the queue meets first.
• Keeping the column in a field of the node changes the tree. Keep it next to the node in the line, as above.
• An empty tree. Return an empty list before touching the queue.

What interviewers ask next

• Bottom view: the same walk, but always overwrite, so the last node seen in each column wins (first.put instead of putIfAbsent).
• Vertical order: keep every node of each column in a list, not just one.
• Vertical sum: add the values of each column instead of keeping one.
• Why not a TreeMap with the queue? It works and is shorter, but costs O(n log n). Tracking lo and hi keeps it O(n).

Remember this

Grown-up words: the post number is the horizontal distance, the floor is the level or depth, the floor by floor walk is breadth first search with a queue, the notebook is a hash map, and the sorted notebook in Way 1 is a TreeMap.