Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Bottom View of Binary Tree

MEDIUMProblemSolveExternal Links

Description

Given the root of a binary tree, return the bottom view of the tree. The bottom view is the set of nodes visible when the tree is viewed from directly below.

Imagine looking up at the tree from the ground. At each horizontal position, the node you see is the one farthest from the root (the deepest one). If multiple nodes share the same horizontal position and the same depth, the one appearing later in level-order traversal is selected.

Return the visible nodes ordered from the leftmost position to the rightmost position.

Key Concept — Horizontal Distance (HD):

  • The root node has an HD of 0.
  • Moving to a left child decreases HD by 1.
  • Moving to a right child increases HD by 1.
  • Among all nodes at the same HD, the deepest one is visible from the bottom. If there is a tie in depth, the node that appears later in level-order traversal wins.

Examples

Example 1

Input: root = [1, 2, 3, 4, 5, N, 6]

      1
     / \
    2   3
   / \   \
  4   5   6

Output: [4, 2, 5, 3, 6]

Explanation:

  • HD = -2: node 4 (only node at this position)
  • HD = -1: node 2 (only node)
  • HD = 0: nodes 1 (depth 0) and 5 (depth 2). Node 5 is deeper → visible from the bottom.
  • HD = 1: node 3 (only node)
  • HD = 2: node 6 (only node)

Node 1 is hidden because node 5 sits directly below it at the same horizontal position.

Example 2

Input: root = [20, 8, 22, 5, 3, 4, 25, N, N, 10, 14, N, N, 28, N]

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

Output: [5, 10, 4, 28, 25]

Explanation:

  • HD = -2: node 5
  • HD = -1: nodes 8 (depth 1) and 10 (depth 3). Node 10 is deeper → visible.
  • HD = 0: nodes 20 (depth 0), 3 (depth 2), and 4 (depth 2). Nodes 3 and 4 share the same depth, but node 4 appears later in level-order → node 4 is visible.
  • HD = 1: nodes 22 (depth 1), 14 (depth 3), and 28 (depth 3). Nodes 14 and 28 share the same depth, but node 28 appears later in level-order → node 28 is visible.
  • HD = 2: node 25

Constraints

  • 1 ≤ number of nodes ≤ 10^5
  • 1 ≤ node.data ≤ 10^5

Editorial

DFS with Depth Tracking

Intuition

A natural first approach is to traverse the entire tree using Depth-First Search (DFS), recording the bottom-most node at each horizontal distance.

As we traverse, each node gets an HD (root = 0, left child = parent HD - 1, right child = parent HD + 1) and a depth (root = 0, children = parent depth + 1). We store each HD's best candidate in an ordered map as a (value, depth) pair.

The key difference from the top view problem is the update rule. For the bottom view, we want the deepest node at each HD. So we update the map entry whenever we encounter a node whose depth is greater than or equal to the stored depth. The "equal to" part ensures that when two nodes share the same HD and depth, the one visited later in DFS overwrites the earlier one — which aligns with the level-order tie-breaking rule for preorder DFS.

Think of it like stacking transparent slides on a projector. Each slide has a drawing at some position. When you look from below, you see the bottom slide at each position — the one laid down last at the deepest layer.

Binary tree with nodes labeled by horizontal distance, showing bottom view visible nodes in green and hidden nodes in red
Binary tree with nodes labeled by horizontal distance, showing bottom view visible nodes in green and hidden nodes in red

Step-by-Step Explanation

Let's trace the DFS approach on the tree from Example 1:

      1
     / \
    2   3
   / \   \
  4   5   6

We perform a preorder DFS (visit → left → right) and track each node's horizontal distance (HD) and depth. We update the map when depth >= stored depth (deeper or equal wins).

Step 1: Visit root node 1.

  • HD = 0, Depth = 0
  • HD 0 is new in the map → store map[0] = (value=1, depth=0)

Step 2: DFS left to node 2.

  • HD = -1, Depth = 1
  • HD -1 is new → store map[-1] = (value=2, depth=1)

Step 3: DFS left to node 4.

  • HD = -2, Depth = 2
  • HD -2 is new → store map[-2] = (value=4, depth=2)

Step 4: Node 4 has no children. Backtrack to node 2 and DFS right to node 5.

  • HD = 0, Depth = 2
  • HD 0 already has (value=1, depth=0). Current depth 2 ≥ stored depth 0 → node 5 is deeper. UPDATE map[0] = (value=5, depth=2). Node 5 replaces node 1!

Step 5: Backtrack to root 1. DFS right to node 3.

  • HD = 1, Depth = 1
  • HD 1 is new → store map[1] = (value=3, depth=1)

Step 6: DFS right to node 6.

  • HD = 2, Depth = 2
  • HD 2 is new → store map[2] = (value=6, depth=2)

Step 7: DFS complete. Sort map keys by HD: [-2, -1, 0, 1, 2].
Collect values: [4, 2, 5, 3, 6]. Node 1 was replaced by the deeper node 5 at HD 0.

DFS Bottom View — Preorder with Depth Tracking — Watch how DFS traverses the tree and overwrites the map entry when a deeper node is found at the same horizontal distance. Node 5 replaces node 1 at HD=0 because it is deeper.

Algorithm

  1. Create an ordered map to store (node value, depth) for each horizontal distance
  2. Perform a preorder DFS starting from the root with HD = 0 and depth = 0:
    • If the current HD is not in the map, store the node
    • If the current HD is already in the map, update if current depth ≥ stored depth (deeper or equal wins)
    • Recurse left with HD - 1 and depth + 1
    • Recurse right with HD + 1 and depth + 1
  3. Iterate through the map keys in sorted order (leftmost to rightmost HD)
  4. Collect the node values and return them

Code

#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    void dfs(Node* node, int hd, int depth,
             map<int, pair<int, int>>& bottomNodes) {
        if (!node) return;

        if (bottomNodes.find(hd) == bottomNodes.end() ||
            depth >= bottomNodes[hd].second) {
            bottomNodes[hd] = {node->data, depth};
        }

        dfs(node->left, hd - 1, depth + 1, bottomNodes);
        dfs(node->right, hd + 1, depth + 1, bottomNodes);
    }

    vector<int> bottomView(Node* root) {
        map<int, pair<int, int>> bottomNodes;
        dfs(root, 0, 0, bottomNodes);

        vector<int> result;
        for (auto& [hd, p] : bottomNodes) {
            result.push_back(p.first);
        }
        return result;
    }
};
class Solution:
    def bottomView(self, root):
        if not root:
            return []

        bottom_nodes = {}

        def dfs(node, hd, depth):
            if not node:
                return
            if hd not in bottom_nodes or depth >= bottom_nodes[hd][1]:
                bottom_nodes[hd] = (node.data, depth)
            dfs(node.left, hd - 1, depth + 1)
            dfs(node.right, hd + 1, depth + 1)

        dfs(root, 0, 0)

        result = []
        for hd in sorted(bottom_nodes.keys()):
            result.append(bottom_nodes[hd][0])
        return result
import java.util.*;

class Solution {
    void dfs(Node node, int hd, int depth,
             TreeMap<Integer, int[]> bottomNodes) {
        if (node == null) return;

        if (!bottomNodes.containsKey(hd) ||
            depth >= bottomNodes.get(hd)[1]) {
            bottomNodes.put(hd, new int[]{node.data, depth});
        }

        dfs(node.left, hd - 1, depth + 1, bottomNodes);
        dfs(node.right, hd + 1, depth + 1, bottomNodes);
    }

    public ArrayList<Integer> bottomView(Node root) {
        TreeMap<Integer, int[]> bottomNodes = new TreeMap<>();
        dfs(root, 0, 0, bottomNodes);

        ArrayList<Integer> result = new ArrayList<>();
        for (int[] entry : bottomNodes.values()) {
            result.add(entry[0]);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

The DFS visits all n nodes, which takes O(n). Each insertion into the ordered map (std::map in C++, TreeMap in Java) costs O(log n). With n insertions, the total map operations cost O(n log n). In Python, sorting the dictionary keys at the end also costs O(k log k) where k ≤ n. Hence the overall time is O(n log n).

Space Complexity: O(n)

The recursion stack can go as deep as the height of the tree, which is O(n) in the worst case (skewed tree). The map stores at most n entries. Total space: O(n).

Why This Approach Is Not Efficient

The DFS approach works correctly but introduces unnecessary complexity:

1. Depth Tracking Overhead: DFS visits nodes in depth-first order, not level by level. A node at depth 5 might be visited before a node at depth 3 at the same HD. This forces us to store and compare depths at every step, adding both code complexity and potential for bugs (getting the >= vs > condition wrong is a common mistake).

2. Ordered Map Cost: To output nodes from leftmost to rightmost HD, we use an ordered map with O(log n) per insert, yielding O(n log n) total. With an unordered map plus sorting at the end, we still pay O(n log n) for the sort.

3. Unnecessary Comparison Logic: Each visit requires checking "is this depth ≥ stored depth?" — a condition that only exists because DFS processes nodes out of level-order.

Key Insight: BFS (level-order traversal) processes all nodes at depth d before any node at depth d+1. This means we can simply overwrite the map entry every time we visit a node at a given HD — no depth tracking, no comparisons. The last value written is guaranteed to be from the deepest level (or the latest at the same depth in level-order). Combined with a hash map and min/max HD tracking, this eliminates both the O(log n) overhead and all comparison logic.

Optimal — BFS Simple Overwrite

Intuition

BFS processes nodes level by level — first all nodes at depth 0, then depth 1, then depth 2, and so on. This gives us a remarkable simplification for the bottom view problem.

Since we want the deepest node at each horizontal distance, and BFS naturally visits shallower nodes before deeper ones, we can simply overwrite the map entry every time we see a node at a given HD. There is no need to track depth or compare levels. The last value written to each HD is automatically from the deepest level.

For nodes at the same HD and same depth, BFS also naturally processes them in left-to-right order (children are enqueued left before right). The last one enqueued at that level is the rightmost, which matches the tie-breaking rule.

To collect results from leftmost to rightmost without sorting, we track the minimum and maximum HD during traversal and iterate that range at the end.

Think of it like rain falling on the tree. Water drips straight down from each horizontal position. The node the raindrop hits last (the deepest one) is what you see from below. BFS naturally walks through the tree top-to-bottom, so the last hit at each position is the answer.

Step-by-Step Explanation

Let's trace the BFS approach on the same tree from Example 1:

      1
     / \
    2   3
   / \   \
  4   5   6

In BFS, we simply overwrite the map entry every time. No depth tracking needed.

Step 1: Initialize queue with (root=1, HD=0). Map is empty. minHD = 0, maxHD = 0.

Step 2: Dequeue node 1 (HD=0).

  • Store map[0] = 1 (first write at HD 0)
  • Enqueue children: (2, HD=-1) and (3, HD=1)

Step 3: Dequeue node 2 (HD=-1).

  • Store map[-1] = 2. Update minHD = -1.
  • Enqueue children: (4, HD=-2) and (5, HD=0)

Step 4: Dequeue node 3 (HD=1).

  • Store map[1] = 3. Update maxHD = 1.
  • Enqueue right child: (6, HD=2)

Step 5: Dequeue node 4 (HD=-2).

  • Store map[-2] = 4. Update minHD = -2.
  • No children. This is the leftmost visible node.

Step 6: Dequeue node 5 (HD=0).

  • OVERWRITE map[0] = 5 (was 1). No "if" check needed — we just write. Node 5 is at depth 2, deeper than node 1 at depth 0. The overwrite naturally picks the deeper node.

Step 7: Dequeue node 6 (HD=2).

  • Store map[2] = 6. Update maxHD = 2.
  • No children. This is the rightmost visible node.

Step 8: Queue empty. Iterate from minHD (-2) to maxHD (2) and collect values.
Result: [4, 2, 5, 3, 6].

BFS Bottom View — Level-Order Simple Overwrite — Watch how BFS overwrites the map at every step without any depth comparison. Since BFS processes top-to-bottom, the last write at each HD is automatically from the deepest level. Node 5 naturally replaces node 1 at HD=0.

Algorithm

  1. If root is null, return an empty list
  2. Create a hash map (HD → node value) and a queue storing (node, HD) pairs
  3. Enqueue the root with HD = 0. Initialize minHD = 0 and maxHD = 0
  4. While the queue is not empty:
    • Dequeue the front (node, HD)
    • Update minHD = min(minHD, HD) and maxHD = max(maxHD, HD)
    • Always write map[HD] = node.data (overwrite unconditionally)
    • If node has a left child, enqueue (left, HD - 1)
    • If node has a right child, enqueue (right, HD + 1)
  5. Iterate from minHD to maxHD and collect map values into the result
  6. Return the result

Code

#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> bottomView(Node* root) {
        if (!root) return {};

        unordered_map<int, int> bottomNodes;
        queue<pair<Node*, int>> q;
        q.push({root, 0});
        int minHd = 0, maxHd = 0;

        while (!q.empty()) {
            auto [node, hd] = q.front();
            q.pop();

            minHd = min(minHd, hd);
            maxHd = max(maxHd, hd);

            // Always overwrite — last write wins
            bottomNodes[hd] = node->data;

            if (node->left)
                q.push({node->left, hd - 1});
            if (node->right)
                q.push({node->right, hd + 1});
        }

        vector<int> result;
        for (int i = minHd; i <= maxHd; i++) {
            result.push_back(bottomNodes[i]);
        }
        return result;
    }
};
from collections import deque

class Solution:
    def bottomView(self, root):
        if not root:
            return []

        bottom_nodes = {}
        queue = deque([(root, 0)])
        min_hd, max_hd = 0, 0

        while queue:
            node, hd = queue.popleft()
            min_hd = min(min_hd, hd)
            max_hd = max(max_hd, hd)

            # Always overwrite — last write wins
            bottom_nodes[hd] = node.data

            if node.left:
                queue.append((node.left, hd - 1))
            if node.right:
                queue.append((node.right, hd + 1))

        return [bottom_nodes[i] for i in range(min_hd, max_hd + 1)]
import java.util.*;

class Solution {
    public ArrayList<Integer> bottomView(Node root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Map<Integer, Integer> bottomNodes = new HashMap<>();
        Queue<Object[]> q = new LinkedList<>();
        q.add(new Object[]{root, 0});
        int minHd = 0, maxHd = 0;

        while (!q.isEmpty()) {
            Object[] curr = q.poll();
            Node node = (Node) curr[0];
            int hd = (int) curr[1];

            minHd = Math.min(minHd, hd);
            maxHd = Math.max(maxHd, hd);

            // Always overwrite — last write wins
            bottomNodes.put(hd, node.data);

            if (node.left != null)
                q.add(new Object[]{node.left, hd - 1});
            if (node.right != null)
                q.add(new Object[]{node.right, hd + 1});
        }

        for (int i = minHd; i <= maxHd; i++) {
            result.add(bottomNodes.get(i));
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

The BFS visits every node exactly once, which takes O(n). Each hash map write is O(1) on average. At the end, iterating from minHD to maxHD takes O(w) where w is the width of the tree, which is at most n. Total: O(n).

Space Complexity: O(n)

The queue can hold at most O(n) nodes (the entire bottom level of a complete binary tree has roughly n/2 nodes). The hash map stores at most n entries. Total: O(n).