Bottom View of a Binary Tree: DFS vs BFS Approach

You are given a binary tree. Imagine standing directly below it and looking straight up the bottom view is the set of nodes you'd actually be able to see.

More formally: for every possible horizontal position in the tree, the bottom view keeps only the deepest node sitting at that position. Nodes that are hidden behind a deeper node at the same horizontal position don't make the cut.

Given the root of a binary tree, return its bottom view as a list of values, ordered from left to right.

Consider this tree:

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

The bottom view of this tree is:

5, 10, 3, 14, 25

Understanding the Problem First

The phrase "horizontal position" is doing all the work here, so let's make it concrete before touching any code.

Picture drawing a vertical line straight down through the root. That's position 0. Every time you move one step to the left child, you shift one position to the left (-1); every step to a right child shifts you one position to the right (+1). This value is usually called the horizontal distance (HD) of a node.

For our tree:

• 20 sits at HD 0 (it's the root).
• 8 is 20's left child → HD -1.
• 22 is 20's right child → HD +1.
• 5 and 3 are 8's children → HD -2 and HD 0 respectively.
• 25 is 22's right child → HD +2.
• 10 and 14 are 3's children → HD -1 and HD +1 respectively.

Now group nodes by HD:

Notice that some HD values have more than one node that's exactly the situation the bottom view rule is meant to resolve. At HD -1, both 8 and 10 sit on the same vertical line, but 10 is further down, so it's the one that would actually be visible from below. Same story at HD 0 (3 wins over 20) and HD +1 (14 wins over 22).

So the real problem boils down to this: for every distinct HD, find the deepest node, then read those winning values off from the smallest HD to the largest.

That reframing is what makes the rest of this article click every approach below is really just a different strategy for visiting nodes and deciding, at each HD, whether the node in hand should replace whatever's currently recorded there.

Setting Up the Tree

We'll use the same tree throughout this article. Here's the plain Java representation:

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class SampleTree {
    public static TreeNode build() {
        TreeNode n20 = new TreeNode(20);
        TreeNode n8  = new TreeNode(8);
        TreeNode n22 = new TreeNode(22);
        TreeNode n5  = new TreeNode(5);
        TreeNode n3  = new TreeNode(3);
        TreeNode n25 = new TreeNode(25);
        TreeNode n10 = new TreeNode(10);
        TreeNode n14 = new TreeNode(14);

        n20.left = n8;
        n20.right = n22;
        n8.left = n5;
        n8.right = n3;
        n22.right = n25;
        n3.left = n10;
        n3.right = n14;

        return n20;
    }
}

Approach 1: The Naive Attempt (and Why It Breaks)

The most instinctive first attempt looks something like this: walk the tree with a normal DFS, track each node's horizontal distance as you go and every time you land on a node, just write its value into a map keyed by HD overwriting whatever was there before. Whatever's left in the map once the traversal finishes should be the bottom view, right?

It's a reasonable guess and it even seems to work at first glance. The trouble is, it quietly assumes something that isn't actually true: that a node visited later in the traversal is always deeper in the tree. That assumption holds sometimes and fails other times and it's not obvious which case you're in until you trace through a real example.

Tracing Through It

A standard preorder DFS (root, then left subtree, then right subtree) visits our tree in this order:

20 → 8 → 5 → 3 → 10 → 14 → 22 → 25

Walking through this while overwriting the map at each HD:

Look closely at step 7. We had already correctly recorded 14 (depth 3) at HD +1, but then 22 (depth 1) comes along later in the traversal and overwrites it purely because DFS happened to visit 22 after 14, not because 22 is actually deeper.

The reason this happens: preorder DFS finishes exploring the entire left subtree before it ever touches the right subtree. So 22, which lives in the right subtree and is fairly shallow, ends up visited after 14, which lives deep inside the left subtree even though 14 is the one that should win.

The final (wrong) output from this approach is:

5, 10, 3, 22, 25

...when the correct answer is 5, 10, 3, 14, 25. The bug is subtle precisely because it doesn't show up everywhere only at the one HD where a shallow right-side node happens to share a column with a deep left-side node.

The Fix, in One Sentence

We need a way to tell the difference between "this node is new information" and "this node is old information arriving late." That means we can't just track values per HD we need to also track how deep each recorded node actually is.

Approach 2: DFS With Depth Tracking (Correct)

This approach keeps the same DFS traversal, but fixes the blind spot from Approach 1 by remembering, for each HD, not just the node's value but also its depth. When a new node arrives at an HD that's already been recorded, we only let it overwrite the existing entry if it's at the same depth or deeper. A shallower latecomer like 22 no longer gets to bulldoze a correct, deeper answer.

Tracing Through It

Same preorder traversal 20 → 8 → 5 → 3 → 10 → 14 → 22 → 25 but now every entry carries a depth and we check before overwriting:

This time, 22 shows up at step 7, checks the depth of the current occupant at HD +1, sees that 14 is deeper and politely backs off. The final map, read from the smallest HD to the largest, gives us:

5, 10, 3, 14, 25

which finally matches the correct answer.

// Java Code
import java.util.*;

public class BottomViewDFS {

    static class NodeInfo {
        int value;
        int depth;

        NodeInfo(int value, int depth) {
            this.value = value;
            this.depth = depth;
        }
    }

    public static List<Integer> bottomView(TreeNode root) {
        TreeMap<Integer, NodeInfo> hdMap = new TreeMap<>();
        fillMap(root, 0, 0, hdMap);
        List<Integer> result = new ArrayList<>();
        for (NodeInfo info : hdMap.values()) {
            result.add(info.value);
        }
        return result;
    }

    private static void fillMap(TreeNode node, int hd, int depth, TreeMap<Integer, NodeInfo> hdMap) {
        if (node == null) return;
        NodeInfo existing = hdMap.get(hd);
        // Only replace the current occupant if this node is at
        // an equal or deeper level  this is the fix from Approach 1
        if (existing == null || depth >= existing.depth) {
            hdMap.put(hd, new NodeInfo(node.val, depth));
        }
        fillMap(node.left, hd - 1, depth + 1, hdMap);
        fillMap(node.right, hd + 1, depth + 1, hdMap);
    }
    public static void main(String[] args) {
        TreeNode root = SampleTree.build();
        System.out.println(bottomView(root));
        // Output: [5, 10, 3, 14, 25]
    }
}

Complexity

This works correctly, but there's still something a little unsatisfying about it we had to bolt on extra bookkeeping (the depth field) just to patch a hole that DFS's traversal order created in the first place. That's usually a hint that a different traversal order might sidestep the problem entirely.

Approach 3: BFS / Level Order Traversal (Optimal)

Here's the observation that makes this approach click: the only reason Approach 1 broke was that DFS doesn't visit nodes in order of depth. A node from a shallow level can get visited after a node from a deep level, simply because of how DFS dives into subtrees.

BFS doesn't have that problem. By definition, a level-order traversal visits every node at depth 0, then every node at depth 1, then depth 2 and so on it is impossible for a shallower node to be visited after a deeper one. Which means: if we just overwrite the map unconditionally as we go, exactly like our buggy Approach 1 did, it will now work correctly because by the time a later node writes over an earlier one, it's guaranteed to be at an equal or greater depth. We get the correctness of Approach 2, without needing to track depth at all.

Tracing Through It

Level order traversal of our tree visits nodes level by level, left to right:

20 → 8 → 22 → 5 → 3 → 25 → 10 → 14

Overwriting the map unconditionally as each node is dequeued:

At step 8, 14 overwrites 22 and this time it's guaranteed correct, since 14 belongs to a later (deeper) level than 22 and BFS never processes a deeper level before a shallower one. No depth field, no comparison logic, no risk of a shallow latecomer sneaking in.

Final result, read left to right by HD:

5, 10, 3, 14, 25

// Java Code
import java.util.*;

public class BottomViewBFS {

    static class QueueEntry {
        TreeNode node;
        int hd;
        QueueEntry(TreeNode node, int hd) {
            this.node = node;
            this.hd = hd;
        }
    }

    public static List<Integer> bottomView(TreeNode root) {
        TreeMap<Integer, Integer> hdMap = new TreeMap<>();
        if (root == null) return new ArrayList<>();
        Queue<QueueEntry> queue = new LinkedList<>();
        queue.add(new QueueEntry(root, 0));
        while (!queue.isEmpty()) {
            QueueEntry current = queue.poll();
            TreeNode node = current.node;
            int hd = current.hd;
            // Safe to overwrite unconditionally: BFS guarantees
            // we never see a shallower node after a deeper one
            hdMap.put(hd, node.val);
            if (node.left != null) {
                queue.add(new QueueEntry(node.left, hd - 1));
            }
            if (node.right != null) {
                queue.add(new QueueEntry(node.right, hd + 1));
            }
        }
        return new ArrayList<>(hdMap.values());
    }
    public static void main(String[] args) {
        TreeNode root = SampleTree.build();
        System.out.println(bottomView(root));
        // Output: [5, 10, 3, 14, 25]
    }
}

• Why TreeMap is used instead of HashMap because the final output must be ordered by horizontal distance (hd), left to right and TreeMap keeps its keys sorted automatically, while HashMap gives no ordering guarantee at all.
• If you did use a HashMap: you'd have to separately track the min and max hd values seen, then loop from min to max and look up each key manually to reconstruct order. That's more code to get the same result TreeMap gives you for free.

Complexity

Comparing All Approaches

n = number of nodes, h = height of the tree, w = width of the tree (number of distinct horizontal distances).

Interestingly, the asymptotic time complexity doesn't actually improve from Approach 2 to Approach 3 both are O(n log w) because of the TreeMap operations. What improves is the simplicity and robustness of the logic: BFS removes an entire category of bugs by construction, rather than patching around them with extra state.

If you want to push the time complexity down to a strict O(n), you can replace the TreeMap with a plain array sized to the tree's width, using the horizontal distance (shifted by an offset so it's never negative) as a direct index. That trades the O(log w) map operations for O(1) array writes, at the cost of a small preprocessing step to figure out the tree's minimum and maximum horizontal distance up front.

Key Takeaways

1. Don't trust traversal order to also mean "visited in the right priority." DFS visiting a node later doesn't mean that node is more important that assumption is exactly what broke Approach 1.
2. When a simple approach almost works, ask what invariant it's silently relying on. Approach 1's real bug wasn't the overwrite logic it was assuming DFS order implies depth order, which is only sometimes true.
3. Sometimes the cleanest fix isn't more logic, it's a different traversal. Approach 2 patches the problem with a depth check; Approach 3 removes the problem by choosing a traversal order (BFS) where that check becomes unnecessary.
4. This HD-and-map pattern shows up everywhere in tree problems. The exact same horizontal-distance bookkeeping is the backbone of "Vertical Order Traversal" and "Top View of a Binary Tree" once you've internalized it here, those problems become variations on a theme rather than new problems entirely.