Top View of Binary Tree in DSA Java

Mental Model

We want to see the nodes that are visible when looking at the tree from above, ignoring nodes hidden behind others.

Analogy: Imagine standing on a balcony looking straight down at a garden with trees; you only see the tops of some trees because others block your view behind them.

       1
      / \
     2   3
      \   \
       4   5

Top view shows nodes: 2 -> 1 -> 3 -> 5

Dry Run Walkthrough

Input: Binary tree: 1 / \ 2 3 \ \ 4 5

Goal: Print nodes visible from the top view: nodes that appear first at each horizontal distance from root.

Step 1: Start BFS from root (1) at horizontal distance (hd) = 0

[Queue: (1, hd=0)]
Top view map: {}

Why: We begin from the root node to explore all nodes level by level.

Step 2: Dequeue (1, hd=0), add 1 to top view map at hd=0

[Queue: (2, hd=-1), (3, hd=1)]
Top view map: {0:1}

Why: First node at hd=0 is 1, so it is visible from top.

Step 3: Dequeue (2, hd=-1), add 2 to top view map at hd=-1

[Queue: (3, hd=1), (4, hd=0)]
Top view map: {-1:2, 0:1}

Why: First node at hd=-1 is 2, so it is visible from top.

Step 4: Dequeue (3, hd=1), add 3 to top view map at hd=1

[Queue: (4, hd=0), (5, hd=2)]
Top view map: {-1:2, 0:1, 1:3}

Why: First node at hd=1 is 3, so it is visible from top.

Step 5: Dequeue (4, hd=0), hd=0 already has node 1, so skip adding 4

[Queue: (5, hd=2)]
Top view map: {-1:2, 0:1, 1:3}

Why: Node 4 is hidden behind node 1 at hd=0.

Step 6: Dequeue (5, hd=2), add 5 to top view map at hd=2

[Queue: ]
Top view map: {-1:2, 0:1, 1:3, 2:5}

Why: First node at hd=2 is 5, so it is visible from top.

Result:

Top view nodes in order of hd: 2 -> 1 -> 3 -> 5

Annotated Code

DSA Java

import java.util.*;

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

public class TopViewBinaryTree {

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

    public static void printTopView(Node root) {
        if (root == null) return;

        Map<Integer, Integer> topViewMap = new TreeMap<>();
        Queue<Pair> queue = new LinkedList<>();

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

        while (!queue.isEmpty()) {
            Pair curr = queue.poll();
            // Add node data if hd not seen before
            if (!topViewMap.containsKey(curr.hd)) {
                topViewMap.put(curr.hd, curr.node.data);
            }

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

        // Print top view nodes in order of horizontal distance
        for (int val : topViewMap.values()) {
            System.out.print(val + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.right.right = new Node(5);

        printTopView(root);
    }
}

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

Start BFS from root at horizontal distance 0

Pair curr = queue.poll();

Dequeue next node to process

if (!topViewMap.containsKey(curr.hd)) { topViewMap.put(curr.hd, curr.node.data); }

Add node data for horizontal distance if not already present

if (curr.node.left != null) { queue.add(new Pair(curr.node.left, curr.hd - 1)); }

Add left child with hd - 1 to queue

if (curr.node.right != null) { queue.add(new Pair(curr.node.right, curr.hd + 1)); }

Add right child with hd + 1 to queue

for (int val : topViewMap.values()) { System.out.print(val + " "); }

Print nodes in order of horizontal distance

Output

2 1 3 5 

Complexity Analysis

Time: O(n) because we visit each node once during BFS traversal

Space: O(n) for the queue and map storing nodes and their horizontal distances

vs Alternative: Naive approach might try to check visibility by scanning levels repeatedly, which is less efficient than BFS with a map.

Edge Cases

Empty tree (root is null)

No output, function returns immediately

DSA Java

if (root == null) return;

Tree with only root node

Prints only the root node

DSA Java

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

Tree with multiple nodes at same horizontal distance

Only the first node encountered at that horizontal distance is printed

DSA Java

if (!topViewMap.containsKey(curr.hd)) { topViewMap.put(curr.hd, curr.node.data); }

When to Use This Pattern

When asked to print nodes visible from the top or bottom of a binary tree, use BFS with horizontal distances and a map to track first or last nodes at each distance.

Common Mistakes

Mistake: Adding nodes to top view map even if a node at that horizontal distance was already added
Fix: Check if horizontal distance key exists before adding to map to ensure only first node is recorded

Mistake: Using DFS which may not process nodes level by level, causing incorrect top view
Fix: Use BFS to process nodes level by level ensuring correct visibility order

Summary

Prints the nodes visible when looking at the binary tree from above.

Use when you need to find the top view of a binary tree showing nodes not hidden behind others.

Track horizontal distances during BFS and record the first node at each distance to get the top view.

Practice

1. What does the top view of a binary tree represent?

easy

A. Nodes visible when the tree is viewed from the right side

B. Nodes visible when the tree is viewed from the left side

C. Nodes visible when the tree is viewed from the top

D. All leaf nodes of the tree

Solution

1. Step 1: Understand the top view concept

   The top view of a binary tree includes all nodes visible when looking down vertically from above the tree.

2. Step 2: Compare with other views

   Left view shows nodes from the left side, right view from the right side, and leaf nodes are only the bottom nodes. So, only top view matches nodes visible from above.

3. Final Answer:

   Nodes visible when the tree is viewed from the top -> Option C

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view shows nodes visible from above the tree [OK]

Common Mistakes:

• Confusing top view with left or right view
• Thinking top view includes all leaf nodes
• Assuming top view is the same as level order traversal

2. Which data structure is commonly used to store nodes while computing the top view of a binary tree in Java?

easy

A. Stack

B. ArrayList

C. HashMap

D. Queue

Solution

1. Step 1: Identify traversal method for top view

   Top view is usually found using level order traversal, which requires a queue to process nodes level by level.

2. Step 2: Understand role of other data structures

   HashMap is used to store horizontal distances but queue is essential to traverse nodes in order. Stack and ArrayList are not suitable for level order traversal.

3. Final Answer:

   Queue -> Option D

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level order traversal in top view [OK]

Common Mistakes:

• Using stack instead of queue for traversal
• Confusing storage with traversal data structure
• Ignoring the need for horizontal distance mapping

3. What is the output of the top view traversal for the following binary tree?

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

medium

A. [2, 1, 3, 4, 7]

B. [2, 1, 3, 5, 7]

C. [2, 1, 4, 6, 7]

D. [1, 2, 3, 4, 5]

Solution

1. Step 1: Assign horizontal distances (HD) to nodes

   Root (1) has HD=0, left child (2) HD=-1, right child (3) HD=1. Node 4 is right child of 2, HD=0. Node 5 is right child of 3, HD=2. Node 6 is right child of 4, HD=1. Node 7 is right child of 5, HD=3.

2. Step 2: Select first node at each HD from top to bottom

   At HD=-1: 2, HD=0: 1, HD=1: 3, HD=2: 5, HD=3: 7. Nodes 4 and 6 are hidden behind 1 and 3 respectively.

3. Final Answer:

   [2, 1, 3, 5, 7] -> Option B

4. Quick Check:

   Top view nodes by HD = [2,1,3,5,7] [OK]

Hint: Pick first node at each horizontal distance [OK]

Common Mistakes:

• Including nodes hidden behind others at same horizontal distance
• Mixing order of nodes in output
• Ignoring horizontal distance calculation

4. Identify the error in this Java snippet for top view of a binary tree:

Map map = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
  Node temp = queue.poll();
  int hd = temp.hd;
  if (!map.containsKey(hd)) {
    map.put(hd, temp.data);
  }
  if (temp.left != null) {
    temp.left.hd = hd - 1;
    queue.add(temp.left);
  }
  if (temp.right != null) {
    temp.right.hd = hd + 1;
    queue.add(temp.right);
  }
}

medium

A. Horizontal distance (hd) is not initialized for root node

B. Using HashMap instead of TreeMap causes wrong order

C. Queue should be a Stack for correct traversal

D. map.put overwrites existing keys causing wrong output

Solution

1. Step 1: Check initialization of horizontal distance

   The root node's horizontal distance (hd) must be set before adding to queue. Here, root.hd is not initialized, so hd is zero by default or undefined.

2. Step 2: Understand impact of missing hd initialization

   Without root.hd set, all subsequent hd calculations are incorrect, leading to wrong top view nodes.

3. Final Answer:

   Horizontal distance (hd) is not initialized for root node -> Option A

4. Quick Check:

   Root hd must be set before traversal [OK]

Hint: Always initialize root horizontal distance before traversal [OK]

Common Mistakes:

• Forgetting to set root.hd = 0
• Using Stack instead of Queue for level order
• Assuming HashMap order is sorted

5. Given a binary tree where multiple nodes share the same horizontal distance, how can you modify the top view algorithm to print nodes in order from leftmost to rightmost horizontal distance?

hard

A. Use a TreeMap to store horizontal distances and their nodes

B. Use a HashSet to track visited nodes only

C. Use a Stack to reverse the order of nodes after traversal

D. Use a LinkedList to store nodes in insertion order

Solution

1. Step 1: Understand the need for ordered horizontal distances

   Top view nodes must be printed from leftmost (lowest HD) to rightmost (highest HD). HashMap does not maintain order.

2. Step 2: Use TreeMap for sorted keys

   TreeMap stores keys in sorted order automatically, so storing HD as keys and node data as values allows ordered traversal for printing.

3. Final Answer:

   Use a TreeMap to store horizontal distances and their nodes -> Option A

4. Quick Check:

   TreeMap keeps keys sorted for ordered output [OK]

Hint: Use TreeMap to keep horizontal distances sorted [OK]

Common Mistakes:

• Using HashMap and expecting sorted output
• Trying to reverse order with stack instead of sorting keys
• Ignoring horizontal distance ordering