Topics › Binary Trees › Medium Problems

Bottom view of BT

Medium TUF ID 115 A2ZSDE

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

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

Give every node a column: the root is in column 0, a left child is in col - 1, a right child is in col + 1. In each column, the node visible from below is the deepest one. If several nodes share the deepest level of a column, the one that comes later in level order (the one further right) is the visible one. That tie rule comes from the GeeksforGeeks statement of this problem, and it is the opposite of the tie rule for the top view.

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

Example 1

          20
        /    \
       8      22
      / \       \
     5   3       25
        / \
       10  14

answer = [5, 10, 3, 14, 25]

Columns: 5 is alone in column -2. Column -1 has 8 (depth 1) and 10 (depth 3), so 10 shows. Column 0 has 20 and 3, so 3 shows. Column 1 has 22 and 14, so 14 shows. Column 2 has only 25.

Example 2

The same tree with 4 added as the left child of 22. Now 3 and 4 are both in column 0 at depth 2. In level order 4 comes after 3, so the answer becomes [5, 10, 4, 14, 25].

Approach 1: DFS that remembers depth

Intuition. “Visible from below” means “largest depth in its column”. Any traversal can find, for each column, the deepest node, as long as every node knows its column and its depth. When we meet a node that is deeper than the one stored for its column, it replaces it.

Ties need care. For nodes at the same depth, a preorder walk that goes left before right visits them from left to right. The reason: for any two such nodes, their lowest common ancestor has one in its left subtree and the other in its right subtree, and preorder finishes the left subtree first. So if we also replace on equal depth (>= rather than >), the last node to be stored at that depth is the rightmost one, which is exactly the “later in level order” rule.

A TreeMap keyed by column returns the columns in sorted order at the end.

Algorithm.

1. Recursively walk the tree with col and depth.
2. At each node, if the column is new, or its stored depth is <= the current depth, store {depth, value}.
3. Recurse left with col - 1 and right 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});  // deeper, or same depth but further right
    dfs(node.left, col - 1, depth + 1, best);
    dfs(node.right, col + 1, depth + 1, best);
}

Complexity. Time O(n log n): one TreeMap lookup and maybe one insert per node. Space O(n) for the map plus O(h) for recursion, where h is the tree height.

Approach 2: BFS with a sorted map

Intuition. Level order visits nodes level by level, and left to right inside a level. So the last node to arrive in a column is the deepest one, and among equally deep nodes it is the rightmost one. That means we can drop the depth entirely and let every arrival overwrite its column with a plain put. Whatever survives at the end is the bottom view.

Compare this with the top view, where putIfAbsent keeps the first arrival. The two problems differ by one method call.

Algorithm.

1. If the tree is empty, return an empty list.
2. BFS over (node, col) pairs, starting with (root, 0). Two parallel queues hold nodes and columns.
3. For each popped pair, put(col, node.val), overwriting any earlier value.
4. Enqueue children with col - 1 and col + 1.
5. 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> bottom = 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();
        bottom.put(col, node.val);                            // later nodes overwrite earlier ones
        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(bottom.values());
    return ans;
}

Complexity. Time O(n log n) for the TreeMap operations. Space O(n).

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

Intuition. The TreeMap is only used to list the columns in order at the end. Columns are contiguous: moving from a parent to a child changes the column by exactly one, so the path from the root to any node passes through every column between 0 and that node’s column. If we track the smallest and largest column seen, every column in between is guaranteed to have a value. A HashMap plus a loop from minCol to maxCol replaces the sorted map and removes the log factor.

Algorithm.

1. If the tree is empty, return an empty list.
2. BFS over (node, col) pairs from (root, 0).
3. For each popped pair: put(col, node.val) and update minCol and maxCol.
4. Append bottom.get(c) for every c from minCol to maxCol.

static List<Integer> optimal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) return ans;
    Map<Integer, Integer> bottom = 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();
        bottom.put(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(bottom.get(c));   // columns are contiguous, so none is missing
    return ans;
}

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

The range is -2..2, so the answer is [5, 10, 4, 14, 25]. Note row 6: 4 overwrites 3 because it arrives later at the same depth.

Complexity. Time O(n): each node enters and leaves the queue once, and hash operations are O(1) on average. Space O(n).

Edge cases and pitfalls

• Empty tree. Return an empty list.
• Strict vs non-strict comparison. In the DFS version, depth > cur[0] would keep the left node on a tie and give [5, 10, 3, 14, 25] for Example 2. The problem wants the later node, so the comparison is >=.
• A shallow node can still be visible. If nothing is below it in its column, the root itself is part of the bottom view (try a tree with only a left child).
• Skewed trees. A chain going only left puts every node in a separate column, so all of them are visible, from the deepest to the root. Recursion depth is n there, which can overflow the Java stack for very deep trees; the BFS versions avoid recursion.
• Several ties at once. The Java tests include a tree where three columns each hold two nodes at the same depth; the right node wins in all three.

Related problems

• Top View of BT is the mirror question: shallowest node per column, left node on ties.
• Vertical Order Traversal keeps every node of every column.
• Right/Left View of Binary Tree picks one visible node per level instead of per column.
• Level Order Traversal is the BFS pattern underneath Approaches 2 and 3.