Top View of Binary Tree in DSA Java - Time & Space Complexity

Time Complexity: Top View of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the top view of a binary tree changes as the tree grows.

How does the number of nodes affect the work done to get the top view?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public void topView(Node root) {
    if (root == null) return;
    Map topViewMap = new TreeMap<>();
    Queue> queue = new LinkedList<>();
    queue.add(new Pair<>(root, 0));
    while (!queue.isEmpty()) {
        Pair temp = queue.poll();
        Node node = temp.getKey();
        int hd = temp.getValue();
        if (!topViewMap.containsKey(hd)) {
            topViewMap.put(hd, node.data);
        }
        if (node.left != null) queue.add(new Pair<>(node.left, hd - 1));
        if (node.right != null) queue.add(new Pair<>(node.right, hd + 1));
    }
    for (int val : topViewMap.values()) {
        System.out.print(val + " ");
    }
}
    

This code prints the top view of a binary tree by visiting nodes level by level and tracking horizontal distances.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that visits each node once using a queue.
• How many times: Exactly once per node in the tree, so n times for n nodes.

How Execution Grows With Input

As the number of nodes grows, the code visits each node once, so the work grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 visits and checks
100	About 100 visits and checks
1000	About 1000 visits and checks

Pattern observation: The operations increase linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the top view grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The top view requires checking all paths, so it must be more than linear time."

[OK] Correct: The code visits each node only once using a queue, so it does not repeat work or check extra paths multiple times.

Interview Connect

Understanding how to analyze tree traversal time helps you explain your approach clearly and confidently in interviews.

Self-Check

"What if we used a recursive approach instead of a queue? How would the time complexity change?"

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