DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Top View of Binary Tree | Level Order Traversal

#algorithms #coding #computerscience #interview

Problem Statement

Given the root of a binary tree, return the nodes visible when the tree is viewed from the top.

For every horizontal distance (HD), only the first node encountered should be included.

Brute Force Intuition

In an interview, you can explain it like this:

Compute the horizontal distance of every node and store all nodes belonging to the same horizontal distance. Finally, choose the topmost node for each horizontal distance.

This requires storing multiple nodes for every horizontal distance.

Complexity

  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Moving Towards the Optimal Approach

Notice that:

BFS

↓

Processes Nodes

Level by Level
Enter fullscreen mode Exit fullscreen mode

The first node encountered for a particular:

Horizontal Distance
Enter fullscreen mode Exit fullscreen mode

will always be the topmost node.

So we only need to store it once.

Pattern Recognition

Whenever you see:

  • Top View
  • Bottom View
  • Vertical Traversal

Think:

Level Order Traversal + Horizontal Distance

Key Observation

Assign every node a:

Horizontal Distance (HD)
Enter fullscreen mode Exit fullscreen mode

Rules:

Root → 0

Left Child → HD - 1

Right Child → HD + 1
Enter fullscreen mode Exit fullscreen mode

If an HD appears for the first time,

store that node.

Ignore all future nodes with the same HD.

Optimal Approach

Step 1

Perform BFS.

Queue stores:

(Node, HD)
Enter fullscreen mode Exit fullscreen mode

Step 2

Maintain:

TreeMap<Integer, Integer>
Enter fullscreen mode Exit fullscreen mode

Key:

Horizontal Distance
Enter fullscreen mode Exit fullscreen mode

Value:

Node Value
Enter fullscreen mode Exit fullscreen mode

Step 3

If HD is not already present:

map.put(hd, node.data);
Enter fullscreen mode Exit fullscreen mode

Step 4

Traverse the TreeMap from left to right.

Optimal Java Solution 

class Pair {

    Node node;
    int hd;

    Pair(Node node, int hd) {

        this.node = node;
        this.hd = hd;
    }
}

class Solution {

    static ArrayList<Integer> topView(Node root) {

        ArrayList<Integer> ans = new ArrayList<>();

        if (root == null)
            return ans;

        Queue<Pair> q = new LinkedList<>();

        TreeMap<Integer, Integer> map =
            new TreeMap<>();

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

        while (!q.isEmpty()) {

            Pair curr = q.poll();

            if (!map.containsKey(curr.hd)) {

                map.put(curr.hd,
                        curr.node.data);
            }

            if (curr.node.left != null)

                q.offer(new Pair(
                    curr.node.left,
                    curr.hd - 1));

            if (curr.node.right != null)

                q.offer(new Pair(
                    curr.node.right,
                    curr.hd + 1));
        }

        ans.addAll(map.values());

        return ans;
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run 

          1
        /   \
       2     3
      / \   / \
     4   5 6   7
Enter fullscreen mode Exit fullscreen mode

Horizontal Distances:

4 → -2

2 → -1

1 → 0

3 → +1

7 → +2
Enter fullscreen mode Exit fullscreen mode

Nodes:

5

6
Enter fullscreen mode Exit fullscreen mode

are ignored because:

HD already occupied
Enter fullscreen mode Exit fullscreen mode

Final Answer:

[4,2,1,3,7]
Enter fullscreen mode Exit fullscreen mode

Why BFS Works?

BFS visits nodes level by level.

The first node encountered at each horizontal distance is always the highest (topmost) node.

Once an HD is recorded,

it should never be replaced.

Complexity Analysis

Metric Complexity
Time Complexity O(N log N)
Space Complexity O(N)

log N comes from inserting keys into the TreeMap.

Interview One-Liner

Perform a level-order traversal while tracking horizontal distances, and store only the first node encountered for each horizontal distance.

Pattern Learned 

BFS

↓

Horizontal Distance

↓

First Node

↓

Top View
Enter fullscreen mode Exit fullscreen mode

Similar Problems

  • Top View of Binary Tree
  • Bottom View of Binary Tree
  • Vertical Order Traversal
  • Vertical Sum
  • Left View
  • Right View

Memory Trick

Think:

Horizontal Distance

↓

Seen Before?

↓

No

↓

Store It

↓

Ignore Future Nodes
Enter fullscreen mode Exit fullscreen mode

Mental Model 

Queue

↓

(Node, HD)

↓

First Node at HD

↓

Answer
Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

"Top View of Binary Tree"

your brain should immediately think:

BFS + Horizontal Distance + First Node

Top comments (0)