Top View of a Binary Tree Using BFS and DFS | Complete Guide

If you've spent any time prepping for interviews at product-based companies, you've probably noticed that binary tree "view" problems top view, bottom view, left view, right view show up constantly. They look deceptively simple on a whiteboard, but the moment you start coding one under interview pressure, it's easy to write something that looks right, passes on the example the interviewer drew and then quietly falls apart on a slightly different tree shape. This article walks through exactly that journey for the top view problem: a first attempt that seems reasonable, why it breaks and how to arrive at a clean, optimal fix.

Problem Statement

You are given the root of a binary tree. Imagine standing far above the tree and looking straight down the top view is the set of nodes you'd actually be able to see from that angle.

More precisely: for every horizontal position in the tree, the top view keeps only the node that's closest to the root at that position. Any node hidden underneath a shallower node at the same horizontal position is left out.

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

For example, for a tree shaped like this:

              1
            /   \
           2     3
            \     \
             4     5
            /     /
           6     7

The top view is:

2, 1, 3, 5

Understanding the Problem First

The key concept here is horizontal distance (HD) the same idea that underlies most binary tree "view" problems, so it's worth being precise about it once and reusing it everywhere.

Draw a vertical line straight down through the root call that position 0. Every time you move to a left child, you shift one step left (-1), every move to a right child shifts one step right (+1). That running total is the node's horizontal distance.

For the tree above:

• 1 is the root → HD 0.
• 2 is 1's left child → HD -1.
• 3 is 1's right child → HD +1.
• 4 is 2's right child → HD 0 (one left, then one right, cancels out).
• 5 is 3's right child → HD +2.
• 6 is 4's left child → HD -1.
• 7 is 5's left child → HD +1.

Grouping by HD:

At HD -1, both 2 and 6 share the same vertical line, but 2 is closer to the root so it's the one that "wins" for the top view. Same story at HD 0 (1 beats 4) and HD +1 (3 beats 7).

So the problem really comes down to: for every distinct HD, find the shallowest node, then read those winners off from the smallest HD to the largest. Every approach below is a different way of deciding, at each HD, whether the node currently in hand should be allowed to claim that spot.

Setting Up the Tree

We'll use the tree from above throughout this article.

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class SampleTree {
    public static TreeNode build() {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);

        n1.left = n2;
        n1.right = n3;
        n2.right = n4;
        n3.right = n5;
        n4.left = n6;
        n5.left = n7;

        return n1;
    }
}

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

A natural first instinct: run a normal DFS, track each node's horizontal distance as you descend and write its value into a map keyed by HD overwriting whatever's already there. Once the traversal finishes, read the map off in order of HD.

This looks tempting because it's almost the same trick you'd reach for on the bottom view problem. The catch is that it quietly assumes the last node visited at a given HD is somehow the "right" one to keep and for top view, that assumption is backwards more often than it's right.

Tracing Through It

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

1 → 2 → 4 → 6 → 3 → 5 → 7

Overwriting the map at every visit:

By the end, three of the four positions are wrong. At HD 0, 4 (depth 2) has overwritten 1 (depth 0) even though 1 is the root and should obviously be visible from the top. At HD -1, 6 (depth 3) has overwritten 2 (depth 1) for the same reason. At HD +1, 7 (depth 3) has overwritten 3 (depth 1).

The naive output ends up as:

6, 4, 7, 5

nowhere close to the correct 2, 1, 3, 5. The root cause: nothing in this approach distinguishes "a node that's genuinely closer to the root" from "a node that simply got visited later in the traversal." DFS's visiting order and a node's actual depth are two very different things and this approach conflates them.

Approach 2: DFS With Depth Tracking (Correct)

The fix is straightforward once you've seen the bug: track each node's depth alongside its value and only let a new node claim an HD if it's strictly shallower than whatever's currently recorded there. A late-arriving deep node like 6 or 7 no longer gets to bulldoze a correct, shallower answer.

Tracing Through It

Same preorder traversal 1 → 2 → 4 → 6 → 3 → 5 → 7 now with depth-aware comparisons:

This time every deep latecomer checks the depth of the current occupant and backs off. Reading the map from the smallest HD to the largest gives us:

2, 1, 3, 5

the correct answer.

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

struct NodeInfo {
    int value;
    int depth;
};

void fillMap(TreeNode* node, int hd, int depth, map<int, NodeInfo>& hdMap) {
    if (node == nullptr) return;
    auto it = hdMap.find(hd);
    // Only claim this HD if we're strictly closer to the root
    // than whoever is currently recorded there
    if (it == hdMap.end() || depth < it->second.depth) {
        hdMap[hd] = {node->val, depth};
    }
    fillMap(node->left, hd - 1, depth + 1, hdMap);
    fillMap(node->right, hd + 1, depth + 1, hdMap);
}
vector<int> topView(TreeNode* root) {
    map<int, NodeInfo> hdMap;
    fillMap(root, 0, 0, hdMap);
    vector<int> result;
    for (auto& [hd, info] : hdMap) {
        result.push_back(info.value);
    }
    return result;
}
int main() {
    TreeNode* root = SampleTree::build();
    vector<int> result = topView(root);
    for (int v : result) cout << v << " ";
    cout << endl;
    // Output: 2 1 3 5
    return 0;
}

using System;
using System.Collections.Generic;

public class NodeInfo {
    public int Value;
    public int Depth;
    public NodeInfo(int value, int depth) {
        Value = value;
        Depth = depth;
    }
}
public class TopViewDFS {
    public static List<int> TopView(TreeNode root) {
        SortedDictionary<int, NodeInfo> hdMap = new SortedDictionary<int, NodeInfo>();
        FillMap(root, 0, 0, hdMap);
        List<int> result = new List<int>();
        foreach (var info in hdMap.Values) {
            result.Add(info.Value);
        }
        return result;
    }
    private static void FillMap(TreeNode node, int hd, int depth, SortedDictionary<int, NodeInfo> hdMap) {
        if (node == null) return;
        NodeInfo existing = hdMap.ContainsKey(hd) ? hdMap[hd] : null;
        // Only claim this HD if we're strictly closer to the root
        // than whoever is currently recorded there
        if (existing == null || depth < existing.Depth) {
            hdMap[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();
        List<int> result = TopView(root);
        Console.WriteLine(string.Join(", ", result));
        // Output: 2, 1, 3, 5
    }
}

import java.util.*;

public class TopViewDFS {
    static class NodeInfo {
        int value;
        int depth;
        NodeInfo(int value, int depth) {
            this.value = value;
            this.depth = depth;
        }
    }
    public static List<Integer> topView(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 claim this HD if we're strictly closer to the root
        // than whoever is currently recorded there
        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(topView(root));
        // Output: [2, 1, 3, 5]
    }
}

class NodeInfo:
    def __init__(self, value, depth):
        self.value = value
        self.depth = depth

def top_view(root):
    hd_map = {}
    fill_map(root, 0, 0, hd_map)
    result = []
    for hd in sorted(hd_map.keys()):
        result.append(hd_map[hd].value)
    return result

def fill_map(node, hd, depth, hd_map):
    if node is None:
        return
    existing = hd_map.get(hd)
    # Only claim this HD if we're strictly closer to the root
    # than whoever is currently recorded there
    if existing is None or depth < existing.depth:
        hd_map[hd] = NodeInfo(node.val, depth)
    fill_map(node.left, hd - 1, depth + 1, hd_map)
    fill_map(node.right, hd + 1, depth + 1, hd_map)

if __name__ == "__main__":
    root = SampleTree.build()
    result = top_view(root)
    print(result)
    # Output: [2, 1, 3, 5]

Complexity

This is correct, but notice we only needed the depth field to patch a problem that DFS's traversal order created in the first place. That's usually worth a second look a different traversal might make the whole comparison unnecessary.

Approach 3: BFS / Level Order Traversal (Optimal)

Here's the mirror image of what made the bottom view problem's BFS solution elegant. In that problem, we wanted the deepest node at each HD and BFS's guarantee shallower levels are always fully processed before deeper ones meant we could safely overwrite the map unconditionally, since later writes were always at least as deep.

For top view, we want the shallowest node instead. The same BFS guarantee flips the logic: since shallower levels are always visited first, the first time we see a given HD, we're already looking at the shallowest possible node for that position. So instead of overwriting, we do the opposite we add an entry only if that HD hasn't been claimed yet and simply ignore every later arrival.

Tracing Through It

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

1 → 2 → 3 → 4 → 5 → 6 → 7

Adding to the map only when the HD hasn't been seen before:

No depth field, no comparisons just "have we already got an answer for this column?" Final result, read left to right by HD:

2, 1, 3, 5

 
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};
struct QueueEntry {
    TreeNode* node;
    int hd;
};

vector<int> topView(TreeNode* root) {
    map<int, int> hdMap;
    if (root == nullptr) return {};
    queue<QueueEntry> q;
    q.push({root, 0});
    while (!q.empty()) {
        QueueEntry current = q.front();
        q.pop();
        TreeNode* node = current.node;
        int hd = current.hd;
        // Claim this HD only the first time we see it. BFS
        // guarantees that first sighting is always the shallowest
        if (hdMap.find(hd) == hdMap.end()) {
            hdMap[hd] = node->val;
        }
        if (node->left != nullptr) {
            q.push({node->left, hd - 1});
        }
        if (node->right != nullptr) {
            q.push({node->right, hd + 1});
        }
    }
    vector<int> result;
    for (auto& [hd, val] : hdMap) {
        result.push_back(val);
    }
    return result;
}

int main() {
    TreeNode* root = SampleTree::build();
    vector<int> result = topView(root);
    for (int v : result) cout << v << " ";
    cout << endl;
    // Output: 2 1 3 5
    return 0;
}

 
using System;
using System.Collections.Generic;

public class QueueEntry {
    public TreeNode Node;
    public int Hd;
    public QueueEntry(TreeNode node, int hd) {
        Node = node;
        Hd = hd;
    }
}
public class TopViewBFS {
    public static List<int> TopView(TreeNode root) {
        SortedDictionary<int, int> hdMap = new SortedDictionary<int, int>();
        if (root == null) return new List<int>();
        Queue<QueueEntry> queue = new Queue<QueueEntry>();
        queue.Enqueue(new QueueEntry(root, 0));
        while (queue.Count > 0) {
            QueueEntry current = queue.Dequeue();
            TreeNode node = current.Node;
            int hd = current.Hd;
            // Claim this HD only the first time we see it. BFS
            // guarantees that first sighting is always the shallowest
            if (!hdMap.ContainsKey(hd)) {
                hdMap[hd] = node.val;
            }
            if (node.left != null) {
                queue.Enqueue(new QueueEntry(node.left, hd - 1));
            }
            if (node.right != null) {
                queue.Enqueue(new QueueEntry(node.right, hd + 1));
            }
        }
        return new List<int>(hdMap.Values);
    }
    public static void Main(string[] args) {
        TreeNode root = SampleTree.Build();
        List<int> result = TopView(root);
        Console.WriteLine(string.Join(", ", result));
        // Output: 2, 1, 3, 5
    }
}

 
import java.util.*;
public class TopViewBFS {
    static class QueueEntry {
        TreeNode node;
        int hd;
        QueueEntry(TreeNode node, int hd) {
            this.node = node;
            this.hd = hd;
        }
    }
    public static List<Integer> topView(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;
            // Claim this HD only the first time we see it BFS
            // guarantees that first sighting is always the shallowest
            if (!hdMap.containsKey(hd)) {
                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(topView(root));
        // Output: [2, 1, 3, 5]
    }
}

 
from collections import deque

class QueueEntry:
    def __init__(self, node, hd):
        self.node = node
        self.hd = hd

def top_view(root):
    hd_map = {}
    if root is None:
        return []
    queue = deque([QueueEntry(root, 0)])
    while queue:
        current = queue.popleft()
        node = current.node
        hd = current.hd
        # Claim this HD only the first time we see it. BFS
        # guarantees that first sighting is always the shallowest
        if hd not in hd_map:
            hd_map[hd] = node.val
        if node.left is not None:
            queue.append(QueueEntry(node.left, hd - 1))
        if node.right is not None:
            queue.append(QueueEntry(node.right, hd + 1))
    return [hd_map[hd] for hd in sorted(hd_map.keys())]

if __name__ == "__main__":
    root = SampleTree.build()
    result = top_view(root)
    print(result)
    # Output: [2, 1, 3, 5]

Complexity

Comparing All Approaches

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

If you've read a "bottom view" writeup before, you'll notice the optimal BFS logic here is the exact opposite: bottom view overwrites unconditionally to always keep the last (deepest) node seen at each HD, while top view adds only-if-absent to always keep the first (shallowest) one. Same traversal, same map, opposite decision rule.

Just like with bottom view, you can push the time complexity down to a strict O(n) by replacing the TreeMap with a plain array sized to the tree's width, indexing directly by the horizontal distance (shifted by an offset so it's never negative) instead of paying O(log w) per map operation.

Key Takeaways

1. A node visited later isn't automatically "more important." The naive DFS attempt fails because it silently assumes recency in traversal order means something meaningful it doesn't.
2. Top view and bottom view are mirror images of the same idea. Both hinge on horizontal distance; the only real difference is whether you're keeping the shallowest node or the deepest one at each position.
3. BFS removes the need for bookkeeping, it doesn't just add speed. The DFS solution needs a depth field and a comparison to stay correct; BFS's traversal order makes that comparison redundant entirely.
4. This pattern extends directly to other tree-view problems. Left view, right view and vertical order traversal are all built on the same horizontal-distance-plus-traversal-order foundation covered here.

Frequently Asked Questions

Related Articles