Top View of Binary Tree in DSA Python - Deep Dive

Overview - Top View of Binary Tree

What is it?

The top view of a binary tree is the set of nodes visible when the tree is seen from above. Imagine looking down on the tree and noting which nodes you can see without any other nodes blocking them. This view shows the nodes that appear first at each horizontal distance from the root.

Why it matters

Top view helps us understand the structure of a tree in a unique way, revealing which nodes are visible from above. Without this concept, we would miss an important perspective on tree data, which is useful in visualization, network routing, and understanding hierarchical data. It also helps in solving problems where visibility or coverage from a certain angle matters.

Where it fits

Before learning top view, you should understand binary trees, tree traversal methods, and the concept of horizontal distance in trees. After mastering top view, you can explore other tree views like bottom view, left view, right view, and vertical order traversal.

Mental Model

Core Idea

The top view of a binary tree shows the first node visible at each horizontal distance when looking down from above.

Think of it like...

Imagine standing on a balcony looking down at a group of tall trees planted in a line. You only see the tops of the trees that are not hidden behind others from your viewpoint. The top view of a binary tree is like noting which tree tops you can see from above.

Horizontal Distance (HD) from root:

          HD=-2    HD=-1    HD=0    HD=1    HD=2
            |        |       |       |       |
           [ ]      [ ]     [R]     [ ]     [ ]
            |        |       |       |       |
          /   \    /   \   /   \   /   \   /   \

Nodes at each HD are checked from top to bottom; first node at each HD is in top view.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Trees

Concept: Introduce the basic structure of a binary tree and its nodes.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Nodes can have zero, one, or two children. We can represent this with a simple class in Python: class Node: def __init__(self, data): self.data = data self.left = None self.right = None This sets the stage for understanding how nodes relate in a tree.

Result

You can create and connect nodes to form a binary tree structure.

Understanding the basic tree structure is essential because all views, including top view, depend on how nodes connect and relate.

2

Foundation

Horizontal Distance Concept

Concept: Introduce horizontal distance (HD) as a way to measure node positions relative to the root.

Horizontal distance is a number assigned to each node to represent its position relative to the root. The root has HD = 0. For any node: - Its left child has HD = parent's HD - 1 - Its right child has HD = parent's HD + 1 This helps us group nodes vertically and decide which nodes appear in the top view.

Result

You can assign horizontal distances to all nodes in a tree.

Knowing horizontal distance lets us organize nodes by their vertical alignment, which is key to finding the top view.

3

Intermediate

Level Order Traversal with HD Tracking

🤔Before reading on: Do you think a depth-first or breadth-first traversal is better to find the top view? Commit to your answer.

Concept: Use breadth-first (level order) traversal to visit nodes level by level while tracking their horizontal distances.

We use a queue to traverse the tree level by level. Each queue entry stores a node and its HD. We start with the root at HD=0. For each node: - If this HD is not seen before, record the node's data as part of the top view. - Add left child with HD-1 and right child with HD+1 to the queue. This ensures the first node at each HD is captured.

Result

We get the first node encountered at each horizontal distance, which forms the top view.

Using level order traversal ensures nodes closer to the root are processed first, capturing the topmost nodes at each horizontal distance.

4

Intermediate

Implementing Top View Algorithm

🤔Before reading on: Do you think storing nodes in a dictionary keyed by HD is enough to get the top view? Commit to your answer.

Concept: Store nodes in a dictionary keyed by horizontal distance, updating only if the HD is new.

We create an empty dictionary top_view_map = {}. Traverse the tree level order with HD tracking. For each node: - If HD not in top_view_map, set top_view_map[HD] = node.data - Else, skip (because we want the first node at that HD) After traversal, sort keys of top_view_map and print values in order.

Result

A list of node values representing the top view from leftmost to rightmost horizontal distance.

Knowing to record only the first node at each HD prevents overwriting and ensures correct top view.

5

Intermediate

Handling Edge Cases and Empty Trees

Concept: Consider what happens if the tree is empty or has only one node.

If the tree is empty (root is None), the top view is empty. If the tree has only one node, the top view is just that node. These cases should be handled gracefully in code to avoid errors.

Result

Robust top view function that works for all tree sizes.

Handling edge cases prevents runtime errors and ensures your solution is complete.

6

Advanced

Optimizing Space with Ordered Dictionary

🤔Before reading on: Do you think using a normal dictionary preserves the order of horizontal distances? Commit to your answer.

Concept: Use an ordered dictionary or sort keys after traversal to maintain left-to-right order in output.

Python 3.7+ dictionaries preserve insertion order, but horizontal distances may not be inserted in sorted order. To output top view from left to right, sort the keys of the dictionary before printing. Alternatively, use collections.OrderedDict and insert keys in sorted order after traversal.

Result

Top view nodes printed in correct left-to-right order.

Maintaining order of horizontal distances is crucial for correct visual representation of the top view.

7

Expert

Surprising Behavior with Overlapping Nodes

🤔Before reading on: Do you think nodes at the same horizontal distance but different depths can both appear in the top view? Commit to your answer.

Concept: Only the topmost node at each horizontal distance appears in the top view, even if nodes overlap vertically.

When multiple nodes share the same horizontal distance, the node closest to the root (smallest depth) is visible from the top. Nodes deeper in the tree at the same HD are hidden behind the topmost node. This is why level order traversal is used: it visits nodes by depth, ensuring the first node at each HD is the topmost.

Result

Top view excludes nodes hidden behind others at the same horizontal distance.

Understanding this prevents confusion about why some nodes at the same HD are not in the top view.

Under the Hood

The algorithm uses a breadth-first search (level order traversal) combined with horizontal distance tracking. Each node is assigned a horizontal distance relative to the root. A map stores the first node encountered at each horizontal distance. Because BFS visits nodes level by level, the first node at a horizontal distance is the topmost node visible from above. The map is then sorted by horizontal distance to produce the top view.

Why designed this way?

This approach was chosen because BFS naturally processes nodes by increasing depth, ensuring the topmost nodes are recorded first. Using horizontal distance groups nodes vertically, allowing us to identify which nodes align when viewed from above. Alternatives like DFS do not guarantee visiting nodes in top-to-bottom order, which can lead to incorrect top views.

┌───────────────┐
│   Start at    │
│   root (HD=0) │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Use queue for │
│ level order   │
│ traversal     │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ For each node │
│ check HD map  │
│ if HD unseen: │
│ record node   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Add children  │
│ with HD-1 and │
│ HD+1 to queue │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ After traversal│
│ sort HD keys  │
│ output nodes  │
└───────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the top view include all nodes at the same horizontal distance? Commit yes or no.

Common Belief: The top view includes all nodes that share the same horizontal distance from the root.

Reality: Only the first (topmost) node at each horizontal distance is included in the top view; nodes below it are hidden.

Why it matters: Including all nodes at the same horizontal distance would misrepresent the view and cause incorrect results in visualization or algorithms relying on top view.

Quick: Can a depth-first traversal correctly find the top view? Commit yes or no.

Common Belief: Any tree traversal method, including depth-first, can be used to find the top view correctly.

Reality: Depth-first traversal can miss the topmost nodes because it does not guarantee visiting nodes by increasing depth, leading to incorrect top view results.

Why it matters: Using the wrong traversal method causes bugs and incorrect outputs, especially in complex trees.

Quick: Does the order of nodes in the output dictionary always match left to right? Commit yes or no.

Common Belief: The dictionary storing nodes by horizontal distance always preserves the left-to-right order automatically.

Reality: Dictionaries do not guarantee sorted order by horizontal distance; explicit sorting is needed to output the top view correctly from left to right.

Why it matters: Without sorting, the printed top view may appear jumbled, confusing users and breaking visual consistency.

Expert Zone

1

The top view depends on the first node encountered at each horizontal distance during level order traversal, so insertion order and traversal method deeply affect the result.

2

In trees with multiple nodes at the same horizontal distance and depth, the order of insertion into the queue can affect which node appears in the top view.

3

Optimizing for memory, one can avoid storing all nodes by discarding nodes at horizontal distances already recorded, reducing space complexity.

When NOT to use

Top view is not suitable when you need to see all nodes at each horizontal distance or when vertical order traversal is required. For those cases, use vertical order traversal or bottom view algorithms instead.

Production Patterns

In real systems, top view algorithms are used in network visualization to show visible nodes from a vantage point, in graphical rendering engines to determine visible elements, and in hierarchical data analysis to summarize tree structures efficiently.

Connections

Vertical Order Traversal

Builds-on

Understanding top view helps grasp vertical order traversal, which groups nodes by horizontal distance but includes all nodes, not just the topmost.

Breadth-First Search (BFS)

Same pattern

Top view relies on BFS traversal to process nodes level by level, showing how BFS is crucial for problems involving shortest paths or level-based processing.

Line of Sight in Computer Graphics

Analogous concept from a different field

Top view is similar to line of sight calculations in graphics, where only visible surfaces from a viewpoint are rendered, showing cross-domain relevance.

Common Pitfalls

#1 Overwriting nodes at the same horizontal distance instead of keeping the first.

Wrong approach:

top_view_map[hd] = node.data # overwrites existing entry without checking

Correct approach:

if hd not in top_view_map:
top_view_map[hd] = node.data # only set if first time

Root cause:

Misunderstanding that only the first node at each horizontal distance should be recorded.

#2 Using depth-first traversal which visits nodes in unpredictable order for top view.

Wrong approach:

def dfs(node, hd):
if node is None:
return
if hd not in top_view_map:
top_view_map[hd] = node.data
dfs(node.left, hd - 1)
dfs(node.right, hd + 1)

Correct approach:

Use level order traversal with a queue to ensure nodes are visited by depth:
queue = [(root, 0)]
while queue:
node, hd = queue.pop(0)
if hd not in top_view_map:
top_view_map[hd] = node.data
if node.left:
queue.append((node.left, hd - 1))
if node.right:
queue.append((node.right, hd + 1))

Root cause:

Not realizing that DFS does not guarantee visiting nodes in top-to-bottom order.

#3 Printing top view nodes without sorting horizontal distances.

Wrong approach:

for hd in top_view_map:
print(top_view_map[hd], end=' ')

Correct approach:

for hd in sorted(top_view_map):
print(top_view_map[hd], end=' ')

Root cause:

Assuming dictionary keys are ordered by horizontal distance without explicit sorting.

Key Takeaways

Top view of a binary tree shows the first visible node at each horizontal distance when viewed from above.

Horizontal distance is a key concept that helps group nodes vertically relative to the root.

Level order traversal is essential to correctly identify the topmost nodes at each horizontal distance.

Only the first node encountered at each horizontal distance is included in the top view; deeper nodes at the same distance are hidden.

Sorting the recorded nodes by horizontal distance ensures the top view is presented from left to right.

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. All leaf nodes of the tree

D. Nodes visible when the tree is viewed from above

Solution

1. Step 1: Understand the meaning of top view

   The top view of a binary tree shows nodes that are visible when looking down vertically from above the tree.

2. Step 2: Compare with other views

   Left or right views show nodes visible from sides, and leaf nodes are only the bottom nodes, so they are different.

3. Final Answer:

   Nodes visible when the tree is viewed from above -> Option D

4. Quick Check:

   Top view = nodes seen from above [OK]

Hint: Top view means looking down from above the tree [OK]

Common Mistakes:

• Confusing top view with left or right view
• Thinking top view shows all leaf nodes
• Assuming top view includes all nodes

2. Which of the following Python data structures is best suited to store nodes by their horizontal distance for top view calculation?

easy

A. Set

B. List

C. Dictionary

D. Tuple

Solution

1. Step 1: Identify the need for key-value mapping

   We need to map horizontal distances (keys) to nodes (values) to track the first node at each horizontal distance.

2. Step 2: Choose the appropriate data structure

   Dictionaries provide key-value pairs, allowing efficient lookup and insertion by horizontal distance.

3. Final Answer:

   Dictionary -> Option C

4. Quick Check:

   Use dictionary for horizontal distance mapping [OK]

Hint: Use dictionary to map horizontal distance to nodes [OK]

Common Mistakes:

• Using list which is index-based, not key-based
• Using set which stores unique values without keys
• Using tuple which is immutable and not key-value

3. Consider the following binary tree:

        1
       / \
      2   3
       \   \
        4   5

What is the top view of this tree?

medium

A. [2, 1, 3, 5]

B. [1, 2, 4, 5]

C. [2, 1, 3]

D. [1, 4, 5]

Solution

1. Step 1: Assign horizontal distances

   Root (1) is at 0, left child (2) at -1, right child (3) at +1, node 4 at 0 (right of 2), node 5 at +2 (right of 3).

2. Step 2: Select first nodes at each horizontal distance

   At -1: 2, at 0: 1 (4 is below 1), at +1: 3, at +2: 5.

3. Final Answer:

   [2, 1, 3, 5] -> Option A

4. Quick Check:

   Top view nodes by horizontal distance = [2,1,3,5] [OK]

Hint: Pick first node at each horizontal distance from left to right [OK]

Common Mistakes:

• Including node 4 instead of node 1 at horizontal distance 0
• Missing node 5 at horizontal distance +2
• Confusing order of nodes in output

4. The following code snippet is intended to print the top view of a binary tree but has a bug. What is the error?

from collections import deque

def top_view(root):
    if not root:
        return []
    q = deque([(root, 0)])
    hd_node = {}
    while q:
        node, hd = q.pop()
        if hd not in hd_node:
            hd_node[hd] = node.data
        if node.left:
            q.append((node.left, hd - 1))
        if node.right:
            q.append((node.right, hd + 1))
    return [hd_node[hd] for hd in sorted(hd_node)]

medium

A. Using q.pop() instead of q.popleft() causes wrong traversal order

B. hd_node dictionary is not initialized correctly

C. The horizontal distance is not updated properly

D. The function does not handle empty trees

Solution

1. Step 1: Analyze queue operations

   The code uses deque as a queue but uses q.pop(), which removes from the right (stack behavior), not from the left (queue behavior).

2. Step 2: Understand traversal order impact

   Top view requires level order traversal (BFS), so nodes must be processed in FIFO order using q.popleft(). Using pop() reverses order and causes incorrect results.

3. Final Answer:

   Using q.pop() instead of q.popleft() causes wrong traversal order -> Option A

4. Quick Check:

   Use popleft() for BFS queue traversal [OK]

Hint: Use popleft() for BFS, pop() is for stack (LIFO) [OK]

Common Mistakes:

• Confusing pop() with popleft() in deque
• Not realizing BFS needs FIFO order
• Thinking dictionary initialization is the problem

5. Given a binary tree where multiple nodes share the same horizontal distance and level, which node should be included in the top view?

hard

A. The node with the maximum value at that horizontal distance

B. The node that appears first in level order traversal at that horizontal distance

C. The node that appears last in level order traversal at that horizontal distance

D. All nodes at that horizontal distance

Solution

1. Step 1: Understand top view node selection

   Top view includes the first node encountered at each horizontal distance during level order traversal (BFS), which means the node closest to the root vertically.

2. Step 2: Eliminate other options

   Maximum value or last node in traversal is not considered; all nodes at same horizontal distance are not included, only the first one.

3. Final Answer:

   The node that appears first in level order traversal at that horizontal distance -> Option B

4. Quick Check:

   Top view = first node at horizontal distance in BFS [OK]

Hint: Pick first node at horizontal distance in BFS order [OK]

Common Mistakes:

• Choosing node by value instead of position
• Including all nodes at same horizontal distance
• Picking last node instead of first in BFS