Top View of Binary Tree in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the 'Top View' of a binary tree represent?

The top view of a binary tree is the set of nodes visible when the tree is viewed from above. It includes the nodes that appear first at each horizontal distance from the root.

beginner

How is horizontal distance (HD) defined in the context of the top view of a binary tree?

Horizontal distance is a measure from the root node where the root has HD = 0. Left child nodes decrease HD by 1, and right child nodes increase HD by 1.

intermediate

Which data structure is commonly used to help find the top view of a binary tree?

A queue is used for level order traversal, and a map or dictionary stores the first node encountered at each horizontal distance.

intermediate

Why do we only keep the first node encountered at each horizontal distance when computing the top view?

Because the first node encountered at a horizontal distance during level order traversal is the topmost node visible from above at that horizontal distance.

intermediate

What is the time complexity of finding the top view of a binary tree using level order traversal?

The time complexity is O(n), where n is the number of nodes, because each node is visited once during the traversal.

What is the horizontal distance of the root node in a binary tree?

A 0

B 1

C -1

D Depends on the tree height

The root node is assigned a horizontal distance of 0 by definition.

Which traversal method is best suited to find the top view of a binary tree?

A Inorder traversal

B Preorder traversal

C Level order traversal

D Postorder traversal

Level order traversal visits nodes level by level, which helps identify the first node at each horizontal distance.

In the top view, if two nodes share the same horizontal distance, which one is visible?

A The leftmost node

B The node at the lower level

C The rightmost node

D The node at the higher level

The node at the higher level (closer to root) is visible from the top view.

What data structure is used to store nodes along with their horizontal distance during traversal?

A Stack

B Queue

C Priority Queue

D Hash Map

A queue is used for level order traversal to process nodes in order.

What is the main purpose of the map/dictionary in the top view algorithm?

A To store the first node at each horizontal distance

B To store all nodes at each horizontal distance

C To store nodes by their depth

D To store nodes in sorted order

The map stores the first node encountered at each horizontal distance to represent the top view.

Explain how to find the top view of a binary tree step-by-step.

Think about how you see the tree from above and which nodes block others.

Why does level order traversal help in finding the top view compared to other traversals?

Consider the order nodes appear when looking from top.

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