Top View of Binary Tree

Problem Link

Top View of Binary Tree – GeeksforGeeks

Problem: Top View of Binary Tree

Problem Statement

Given a binary tree, return the top view of the tree.

The top view of a binary tree is the set of nodes visible when the tree is viewed from the top.
Return the nodes from leftmost to rightmost in the top view.

Examples

Example 1

Input:
        1
      /   \
     2     3
      \   / \
       4 5   6

Output: 2 1 3 6

Example 2

Input:
      10
     /  \
    20  30
          \
          40
            \
            60

Output: 20 10 30 60

Constraints

• 1 <= Number of nodes <= 10⁵

• 1 <= Data of a node <= 10⁵

Intuition

We want to print only the first node visible at each horizontal distance (HD) from the root.

• Perform level-order traversal (BFS) while tracking each node’s horizontal distance.

• Use a map to store the first node encountered at each HD.

• At the end, sort the keys (HDs) and output the corresponding node values.

Approach (BFS with Horizontal Distance Mapping)

Steps

1. Use a TreeMap<Integer, Integer> or HashMap + sorting to store first node at each HD.

2. Use a Queue of Pair<Node, HD> to perform level-order traversal.

3. For each node:

   • If HD is not in map, add it.

   • Enqueue left child with HD - 1 and right child with HD + 1.

4. After traversal, extract values in ascending order of HDs.

Code (Java)

class Solution {
    static class Pair {
        Node node;
        int hd;
        Pair(Node node, int hd) {
            this.node = node;
            this.hd = hd;
        }
    }

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

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

        q.add(new Pair(root, 0));

        while (!q.isEmpty()) {
            Pair current = q.poll();
            Node node = current.node;
            int hd = current.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()) {
            result.add(val);
        }

        return result;
    }
}

Time and Space Complexity

• Time Complexity: O(N log N)
  Due to TreeMap operations for inserting horizontal distances.

• Space Complexity: O(N)
  Queue and map can hold up to N nodes in worst case.

Dry Run

Input:

        1
      /   \
     2     3
      \   / \
       4 5   6

HDs:

• 2 → HD -1

• 4 → HD 0 (already filled by 1)

• 5 → HD 0 (ignored)

• 6 → HD +2

Map after traversal:
{-1: 2, 0: 1, +1: 3, +2: 6}

Output: [2, 1, 3, 6]

Conclusion

• The top view is built using level-order traversal + HD tracking.

• TreeMap helps in ordering nodes by HD from leftmost to rightmost.

• This is a classic application of BFS + hashmap for structured traversal with spatial context.