Top View of Binary Tree

Time: O(n)

Space: O(n)

Intuition

Level-order traversal with horizontal distance (HD). For each HD, record only the FIRST node seen (top view). A node is visible from the top if no ancestor has the same HD.

Algorithm

1BFS with (node, HD). Map: HD â†’ first seen value (only set if HD not already in map).
2Enqueue (left, hdâˆ’1) and (right, hd+1).
3Return map values sorted by HD.

Example Walkthrough

Input: Tree: 1â†’(2â†’(4,5),3)

1.HD: 4â†’-2, 2â†’-1, 5â†’0, 1â†’0, 3â†’1. Top (first seen): 4,2,1,3.

Output: [4,2,1,3]

Common Pitfalls

•For top view, the FIRST node (BFS order = top to bottom) at each HD wins. For bottom view, the last node wins.

Top View of Binary Tree.java

Java

// Approach: BFS with horizontal distance tracking. For each HD, store only the first node encountered.
// Time: O(n) Space: O(n)
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int val) {
        this.data = val;
        this.left = null;
        this.right = null;
    }
}

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

        Map<Integer, Integer> map = new TreeMap<>();
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(root, 0));

        while (!q.isEmpty()) {
            Pair p = q.poll();
            Node node = p.node;
            int hd = p.hd;

            if (!map.containsKey(hd))
                map.put(hd, node.data);

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

        for (int val : map.values())
            ans.add(val);

        return ans;
    }
}

class Pair {
    Node node;
    int hd;

    Pair(Node n, int h) {
        node = n;
        hd = h;
    }
}

Was this solution helpful?