Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Top View of a Binary Tree

MEDIUMProblemSolveExternal Links

Description

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

Imagine looking straight down at a binary tree from the sky. Some nodes may overlap at the same horizontal position. For each horizontal position, only the node closest to the root (the topmost one) is visible.

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.
  • Nodes sharing the same HD are vertically aligned. Among them, only the topmost (closest to the root) appears in the top view.

Examples

Example 1

Input: root = [1, 2, 3]

    1
   / \
  2   3

Output: [2, 1, 3]

Explanation: Node 2 is at HD = -1 (leftmost), node 1 is at HD = 0 (center), and node 3 is at HD = 1 (rightmost). All three nodes are visible from the top since no two nodes share the same horizontal position.

Example 2

Input: root = [10, 20, 30, 40, 60, 90, 100]

         10
        /  \
       20   30
      / \   / \
     40  60 90 100

Output: [40, 20, 10, 30, 100]

Explanation:

  • HD = -2: node 40
  • HD = -1: node 20
  • HD = 0: nodes 10, 60, and 90 all share this position. Node 10 is closest to the root (level 0) so it is the visible one. Nodes 60 and 90 (level 2) are hidden behind it.
  • HD = 1: node 30
  • HD = 2: node 100

Nodes 60 and 90 are blocked by node 10 when viewed from above.

Constraints

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

Editorial

DFS with Level Tracking

Intuition

A natural first thought is to traverse the entire tree and record which node should represent each horizontal distance (HD). We can use Depth-First Search (DFS) for this.

As we traverse, we assign each node an HD: the root gets 0, left children get parent's HD minus 1, and right children get parent's HD plus 1. We also track the depth (level) of each node from the root.

The challenge with DFS is that it does not visit nodes top-to-bottom. A node deep in the tree might be visited before a shallower node at the same HD. To handle this, we store both the value and the level for each HD in an ordered map. When we encounter a node at an HD that is already in the map, we only update the entry if the new node is at a shallower level (closer to the root).

Think of it like exploring a building by taking the stairs down to the basement first before checking the ground floor of another wing. We need to remember which floor we found each room on so we can pick the highest one later.

Binary tree with nodes labeled by their horizontal distance values, showing top view visible nodes in green and hidden nodes in red
Binary tree with nodes labeled by their horizontal distance values, showing top 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 2:

         10
        /  \
       20   30
      / \   / \
     40  60 90 100

We perform a preorder DFS (visit node → left subtree → right subtree) and track each node's horizontal distance (HD) and level (depth from root).

Step 1: Visit root node 10.

  • HD = 0, Level = 0
  • HD 0 is new in the map → store map[0] = (value=10, level=0)

Step 2: DFS left to node 20.

  • HD = -1, Level = 1
  • HD -1 is new → store map[-1] = (value=20, level=1)

Step 3: DFS left to node 40.

  • HD = -2, Level = 2
  • HD -2 is new → store map[-2] = (value=40, level=2)

Step 4: Node 40 has no children. Backtrack to node 20 and DFS right to node 60.

  • HD = 0, Level = 2
  • HD 0 already in map with (value=10, level=0). Current level 2 > stored level 0 → node 10 is higher than node 60. Do NOT update. Node 60 is hidden.

Step 5: Backtrack to root 10. DFS right to node 30.

  • HD = 1, Level = 1
  • HD 1 is new → store map[1] = (value=30, level=1)

Step 6: DFS left to node 90.

  • HD = 0, Level = 2
  • HD 0 already in map with (value=10, level=0). Level 2 > 0 → hidden behind node 10 again. Skip.

Step 7: Backtrack to node 30. DFS right to node 100.

  • HD = 2, Level = 2
  • HD 2 is new → store map[2] = (value=100, level=2)

Step 8: DFS complete. Sort map keys by HD: [-2, -1, 0, 1, 2].
Collect values in order: [40, 20, 10, 30, 100].

DFS Top View — Preorder Traversal with Level Tracking — Watch how DFS traverses the tree depth-first and records the topmost node at each horizontal distance. Nodes 60 and 90 are skipped because node 10 already occupies HD=0 at a shallower level.

Algorithm

  1. Create an ordered map to store (node value, level) for each horizontal distance
  2. Perform a preorder DFS starting from the root with HD = 0 and level = 0:
    • If the current HD is not in the map, store the node
    • If the current HD is already in the map, update only if the current level is smaller (node is closer to root)
    • Recurse left with HD - 1 and level + 1
    • Recurse right with HD + 1 and level + 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 level,
             map<int, pair<int, int>>& topNodes) {
        if (!node) return;

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

        dfs(node->left, hd - 1, level + 1, topNodes);
        dfs(node->right, hd + 1, level + 1, topNodes);
    }

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

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

        top_nodes = {}

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

        dfs(root, 0, 0)

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

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

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

        dfs(node.left, hd - 1, level + 1, topNodes);
        dfs(node.right, hd + 1, level + 1, topNodes);
    }

    static ArrayList<Integer> topView(Node root) {
        TreeMap<Integer, int[]> topNodes = new TreeMap<>();
        dfs(root, 0, 0, topNodes);

        ArrayList<Integer> result = new ArrayList<>();
        for (int[] entry : topNodes.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). However, 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 is the number of unique horizontal distances, which can be up to 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 (one per unique HD). Total space: O(n).

Why This Approach Is Not Efficient

The DFS approach works correctly but has two key inefficiencies:

1. Extra Level Tracking: DFS visits nodes in depth-first order, not top-to-bottom. A deeper node at the same horizontal distance might be visited before a shallower one. This forces us to store the level alongside each value and compare levels on every visit — adding both conceptual and computational overhead.

2. Ordered Map Overhead: To output nodes from leftmost to rightmost, we need the horizontal distances in sorted order. The DFS approach uses an ordered map (std::map in C++, TreeMap in Java), where each insert and lookup costs O(log n). Over n nodes, this gives O(n log n) total time.

Key Insight: If we could process nodes level by level (top to bottom), the first node encountered at each horizontal distance would automatically be the topmost — eliminating the need for level comparisons entirely. Additionally, by tracking the minimum and maximum horizontal distances during traversal and using a hash map (O(1) per operation), we can avoid the sorting overhead.

BFS (level-order traversal) provides exactly this guarantee, reducing the total time from O(n log n) to O(n).

Optimal — BFS with Hash Map

Intuition

Instead of DFS, we use Breadth-First Search (BFS), which processes nodes level by level — first level 0, then level 1, then level 2, and so on.

This is powerful because in BFS, the first time we encounter a particular horizontal distance, the node at that HD is guaranteed to be at the shallowest level. We do not need to track levels or compare depths at all. We simply check: is this HD already in the map? If not, store it. If yes, skip it.

To collect results from leftmost to rightmost without sorting, we track the minimum and maximum HD seen during the traversal. At the end, we iterate from min HD to max HD and look up each value in the hash map. This avoids the O(n log n) sorting cost of the DFS approach.

Think of it like taking a photograph of the tree from a helicopter directly above. As the camera scans from left to right, the first thing it sees at each horizontal column is the topmost node. BFS mimics this by always processing the upper layers first.

Step-by-Step Explanation

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

         10
        /  \
       20   30
      / \   / \
     40  60 90 100

We perform a level-order traversal (BFS) and track each node's horizontal distance. Since BFS processes nodes level by level, the first node at each HD is guaranteed to be the topmost.

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

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

  • HD 0 not in map → store map[0] = 10
  • Enqueue children: (20, HD=-1) and (30, HD=1)

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

  • HD -1 not in map → store map[-1] = 20. Update minHD = -1.
  • Enqueue children: (40, HD=-2) and (60, HD=0)

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

  • HD 1 not in map → store map[1] = 30. Update maxHD = 1.
  • Enqueue children: (90, HD=0) and (100, HD=2)

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

  • HD -2 not in map → store map[-2] = 40. Update minHD = -2.
  • No children. This is the leftmost visible node.

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

  • HD 0 ALREADY in map (node 10 was stored at step 2). Since BFS reached node 10 first (level 0 before level 2), node 10 is the topmost at HD 0. Node 60 is hidden. SKIP.

Step 7: Dequeue node 90 (HD=0).

  • HD 0 ALREADY in map. Another node hidden behind node 10. Two nodes (60 and 90) both tried to claim HD 0 but arrived too late. SKIP.

Step 8: Dequeue node 100 (HD=2).

  • HD 2 not in map → store map[2] = 100. Update maxHD = 2.
  • No children. This is the rightmost visible node.

Step 9: Queue empty. Iterate from minHD (-2) to maxHD (2) and collect values.
Result: [40, 20, 10, 30, 100].

BFS Top View — Level-Order with Horizontal Distance — Watch how BFS naturally processes nodes level by level, so the first node encountered at each horizontal distance is always the topmost. No level tracking is needed — just a simple 'already seen' check.

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)
    • If HD is not in the map, store map[HD] = node.data
    • 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> topView(Node* root) {
        if (!root) return {};

        unordered_map<int, int> topNodes;
        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);

            if (topNodes.find(hd) == topNodes.end()) {
                topNodes[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(topNodes[i]);
        }
        return result;
    }
};
from collections import deque

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

        top_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)

            if hd not in top_nodes:
                top_nodes[hd] = node.data

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

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

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

        Map<Integer, Integer> topNodes = 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);

            topNodes.putIfAbsent(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(topNodes.get(i));
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n)

The BFS visits every node exactly once, which takes O(n). Each hash map insertion and lookup 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 (in the worst case, 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).