Bird
Raised Fist0
DSA Pythonprogramming

Top View of Binary Tree in DSA Python

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Mental Model
We want to see the nodes 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 the trees that are not blocked by others.
       1
      / \
     2   3
    / \   \
   4   5   6

Top view shows nodes: 4, 2, 1, 3, 6
Dry Run Walkthrough
Input: Binary tree: 1 / \ 2 3 / \ \ 4 5 6
Goal: Print nodes visible from the top view: 4 2 1 3 6
Step 1: Start BFS from root (1) at horizontal distance (hd) = 0
[Queue: (1, hd=0)]
Why: We begin from the root to explore all nodes level by level
Step 2: Visit node 1, record hd=0 with node 1 as top view
Top view map: {0:1}
Queue: (2, hd=-1), (3, hd=1)
Why: First node at hd=0 is 1, add children with updated hd
Step 3: Visit node 2 at hd=-1, record it as top view for hd=-1
Top view map: {-1:2, 0:1}
Queue: (3, hd=1), (4, hd=-2), (5, hd=0)
Why: First node at hd=-1 is 2, add children with hd
Step 4: Visit node 3 at hd=1, record it as top view for hd=1
Top view map: {-1:2, 0:1, 1:3}
Queue: (4, hd=-2), (5, hd=0), (6, hd=2)
Why: First node at hd=1 is 3, add right child with hd=2
Step 5: Visit node 4 at hd=-2, record it as top view for hd=-2
Top view map: {-2:4, -1:2, 0:1, 1:3}
Queue: (5, hd=0), (6, hd=2)
Why: First node at hd=-2 is 4, no children to add
Step 6: Visit node 5 at hd=0, hd=0 already recorded, skip
Top view map unchanged
Queue: (6, hd=2)
Why: Node 1 already recorded at hd=0, so 5 is hidden from top
Step 7: Visit node 6 at hd=2, record it as top view for hd=2
Top view map: {-2:4, -1:2, 0:1, 1:3, 2:6}
Queue empty
Why: First node at hd=2 is 6, no children
Result: 
Top view nodes in order of hd: 4 -> 2 -> 1 -> 3 -> 6
Annotated Code
DSA Python
from collections import deque

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def top_view(root):
    if not root:
        return []

    # Map hd to first node value seen
    top_view_map = {}
    # Queue holds pairs of (node, horizontal distance)
    queue = deque([(root, 0)])

    while queue:
        node, hd = queue.popleft()

        # Record the first node at this horizontal distance
        if hd not in top_view_map:
            top_view_map[hd] = node.val

        # Add left child with hd-1
        if node.left:
            queue.append((node.left, hd - 1))

        # Add right child with hd+1
        if node.right:
            queue.append((node.right, hd + 1))

    # Extract values sorted by horizontal distance
    return [top_view_map[hd] for hd in sorted(top_view_map)]

# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.right = Node(6)

result = top_view(root)
print(' -> '.join(map(str, result)) + ' -> null')
queue = deque([(root, 0)])
Initialize queue with root at horizontal distance 0
node, hd = queue.popleft()
Process nodes level by level with their horizontal distance
if hd not in top_view_map: top_view_map[hd] = node.val
Record first node encountered at each horizontal distance
if node.left: queue.append((node.left, hd - 1))
Add left child with horizontal distance one less
if node.right: queue.append((node.right, hd + 1))
Add right child with horizontal distance one more
return [top_view_map[hd] for hd in sorted(top_view_map)]
Return nodes in order from leftmost to rightmost horizontal distance
OutputSuccess
4 -> 2 -> 1 -> 3 -> 6 -> null
Complexity Analysis
Time: O(n) because we visit each node once in BFS
Space: O(n) for the queue and map storing nodes at each horizontal distance
vs Alternative: Naive approach might try to print nodes by vertical lines using DFS with more complex bookkeeping, which can be less efficient
Edge Cases
Empty tree
Returns empty list, no nodes to show
DSA Python
if not root:
    return []
Tree with only root node
Returns list with only root value
DSA Python
queue = deque([(root, 0)])
Tree with multiple nodes at same horizontal distance but different levels
Only the topmost (first encountered in BFS) node at each horizontal distance is recorded
DSA Python
if hd not in top_view_map:
    top_view_map[hd] = node.val
When to Use This Pattern
When asked to print nodes visible from the top or bottom of a binary tree, use horizontal distance with BFS to track first or last nodes at each distance.
Common Mistakes
Mistake: Using DFS instead of BFS causes incorrect top view because deeper nodes might overwrite top nodes
Fix: Use BFS to ensure nodes are processed level by level, capturing the topmost nodes first
Mistake: Not sorting horizontal distances before output leads to unordered results
Fix: Sort the keys of the horizontal distance map before printing
Summary
Prints the nodes visible when looking at the binary tree from above.
Use it when you need to find which nodes appear in the top view of a tree.
The key is to track horizontal distances and record the first node seen at each distance using BFS.

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard