Bottom View of a tree

The problem, simply

You get a binary tree. Give every node a column number. The root is in column 0. Stepping to a left child moves one column to the left (minus 1). Stepping to a right child moves one column to the right (plus 1).

Now look at the tree from below. In each column you only see the node that is lowest. Give back those nodes, from the leftmost column to the rightmost column.

If two nodes share the same column and the same row, the usual rule is to keep the one further right, which is the one you meet later when reading row by row.

A story to remember it

Picture it

Examples

Way 1: the simple way

Walk the tree with a deep dive, carrying the column and the row of each node. For every column, remember the node with the biggest row seen so far. A sorted map keeps the columns in order for us.

1. Start at the root with column 0 and row 0.
2. At each node, look up its column in the sorted map. If the column is empty, or this node's row is the same or deeper, store this node.
3. Go to the left child with column minus 1, then the right child with column plus 1, both one row deeper.
4. Read the map from the smallest column to the biggest.

import java.util.*;

class Solution {
    // column -> {value, row}; a TreeMap keeps columns sorted
    private TreeMap<Integer, int[]> best = new TreeMap<>();

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

    private void dive(TreeNode node, int col, int row) {
        if (node == null) return;
        int[] seen = best.get(col);
        // same row or deeper wins; same row means further right in this order
        if (seen == null || row >= seen[1]) best.put(col, new int[]{node.val, row});
        dive(node.left, col - 1, row + 1);
        dive(node.right, col + 1, row + 1);
    }
}

How long it takes: every node is visited once, but each visit talks to a sorted map, which costs log n. Total O(n log n). Extra room: the map and the dive, O(n).

Way 2: the clever way

Read the tree row by row with a waiting line, a queue. Rows come out from top to bottom, so a later node in a column is always lower (or in the same row and further right). That means we do not need to compare rows at all. We overwrite.

We also do not need a sorted map. Keep a plain map from column to value, plus the smallest and biggest column seen. At the end, walk the columns from smallest to biggest.

1. Put the root in the line with column 0.
2. Take the front node. Write its value into its column, rubbing out whatever was there.
3. Add its left child with column minus 1 and its right child with column plus 1 to the back of the line.
4. When the line is empty, read columns from the smallest to the biggest.

import java.util.*;

class Solution {
    public List<Integer> bottomView(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        if (root == null) return out;
        Map<Integer, Integer> lowest = new HashMap<>();   // column -> value
        Queue<TreeNode> line = new ArrayDeque<>();
        Queue<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 col = cols.poll();
            lowest.put(col, node.val);                     // later means lower, so overwrite
            lo = Math.min(lo, col);
            hi = Math.max(hi, col);
            if (node.left != null) { line.add(node.left); cols.add(col - 1); }
            if (node.right != null) { line.add(node.right); cols.add(col + 1); }
        }
        for (int c = lo; c <= hi; c++) out.add(lowest.get(c));
        return out;
    }
}

How long it takes: every node joins and leaves the line once, and each map step is quick, so O(n). Reading the columns is at most n more steps because columns have no gaps. Extra room: the line and the map, O(n).

Watch out for

• Mixing it up with the top view. Top view keeps the first node in each column. Bottom view keeps the last one.
• Ties in the same row and column. Say which one you keep. Row by row reading keeps the right one.
• Columns have no gaps. If column -2 and column 1 are used, then -1 and 0 are used too, because every node's parent is one column away. That is why the loop from lo to hi never meets an empty column.
• A null root. Return an empty list.

What interviewers ask next

• Top view? Same loop, but only write a column the first time you see it (putIfAbsent).
• Left view and right view? Those are about rows, not columns. Keep the first or last node of each row.
• Vertical order traversal (list every node in each column)? Store a list per column instead of one value. LeetCode 987 also sorts nodes in the same row and column by value.
• Can you avoid the map? Count the leftmost and rightmost column in a first pass, then use an array of size hi - lo + 1 with an offset of -lo.

Remember this

Grown-up words: the floor stripes are columns, also called horizontal distance; reading row by row is breadth first search with a queue; the sorted notebook is a TreeMap; the plain notebook is a HashMap.