Bottom View of Binary Tree in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bottom View for a Simple Binary Tree

What is the output of the bottom view traversal for the given binary tree?

DSA Python

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

def bottom_view(root):
    if not root:
        return []
    from collections import deque
    queue = deque([(root, 0)])
    hd_node_map = {}
    while queue:
        node, hd = queue.popleft()
        hd_node_map[hd] = node.val
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    return [hd_node_map[hd] for hd in sorted(hd_node_map)]

root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.left = Node(40)
root.left.right = Node(50)
root.right.right = Node(60)

print(bottom_view(root))

A [40, 20, 10, 30, 60]

B [40, 20, 50, 30, 60]

C [40, 20, 50, 10, 60]

D [10, 20, 50, 30, 60]

💡 Hint

Remember bottom view shows the last node at each horizontal distance from left to right.

The bottom view keeps the last node encountered at each horizontal distance. For hd -2: 40, hd -1: 20, hd 0: 50 (overwrites 10), hd 1: 30, hd 2: 60.

🧠 Conceptual

intermediate

Horizontal Distance in Bottom View

In the bottom view of a binary tree, what does the horizontal distance (hd) represent?

A The vertical level of the node in the tree.

B The number of nodes in the subtree rooted at the node.

C The depth of the node from the root.

D The distance of the node from the root along the horizontal axis, with left as negative and right as positive.

💡 Hint

Think about how nodes are positioned left or right relative to the root.

Horizontal distance is calculated by moving left (hd - 1) or right (hd + 1) from the root, representing horizontal position.

🔧 Debug

advanced

Identify the Error in Bottom View Implementation

What error will this code produce when computing the bottom view of a binary tree?

DSA Python

def bottom_view(root):
    if not root:
        return []
    queue = [(root, 0)]
    hd_node_map = {}
    while queue:
        node, hd = queue.pop()
        hd_node_map[hd] = node.val
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    return [hd_node_map[hd] for hd in sorted(hd_node_map)]

A The code returns the top view instead of bottom view.

B The code raises an IndexError due to popping from an empty list.

C The code returns nodes in reverse horizontal order.

D The code runs correctly and returns the bottom view list.

💡 Hint

Check how nodes are removed from the queue and how that affects traversal order.

Using pop() removes from the end (LIFO), making traversal depth-first and right-to-left, so the last node at each hd is not the bottom-most but the last visited in reverse order.

❓ Predict Output

advanced

Bottom View Output for Complex Tree

What is the output of the bottom view traversal for this binary tree?

DSA Python

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

def bottom_view(root):
    from collections import deque
    queue = deque([(root, 0)])
    hd_node_map = {}
    while queue:
        node, hd = queue.popleft()
        hd_node_map[hd] = node.val
        if node.left:
            queue.append((node.left, hd - 1))
        if node.right:
            queue.append((node.right, hd + 1))
    return [hd_node_map[hd] for hd in sorted(hd_node_map)]

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

print(bottom_view(root))

A [2, 4, 5, 6]

B [1, 4, 5, 6, 3]

C [2, 5, 6, 3]

D [2, 4, 6, 3]

💡 Hint

Track horizontal distances carefully as nodes go deeper on the right side of left subtree.

Horizontal distances: 1 at hd 0, 2 at hd -1, 3 at hd 1, 4 at hd 0 (overwrites 1), 5 at hd 1 (overwrites 3), 6 at hd 2. Final bottom view is [2, 4, 5, 6].

🚀 Application

expert

Number of Nodes in Bottom View

Given a binary tree, how many nodes will be in the bottom view if the tree is a perfect binary tree of height 3?

A 7

B 5

C 3

D 8

💡 Hint

Consider the horizontal distances for a perfect binary tree of height 3.

A perfect binary tree of height 3 has 15 nodes. Horizontal distances range from -3 to 3, so bottom view has 7 nodes. Nodes at hd -3, -2, -1, 0, 1, 2, 3 are visible. The bottom view includes one node per horizontal distance, so total is 7.

Practice

1. What does the bottom 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 top

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

D. Nodes visible when the tree is viewed from the bottom

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes visible when looking at the tree from below, meaning the lowest nodes at each horizontal distance.

2. Step 2: Compare with other views

   Top view shows nodes from above, left and right views show nodes from sides, so bottom view is unique for bottom perspective.

3. Final Answer:

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

4. Quick Check:

   Bottom view = visible nodes from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal distance [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking bottom view shows all leaf nodes
• Mixing bottom view with side views

2. Which data structure is commonly used to track nodes and their horizontal distances when computing the bottom view of a binary tree?

easy

A. Hash Map (Dictionary)

B. Queue

C. Stack

D. Linked List

Solution

1. Step 1: Identify the need for horizontal distance mapping

   We need to map horizontal distances to nodes to know which node is visible at each position.

2. Step 2: Choose the data structure

   A hash map (dictionary) stores horizontal distance as key and node value as value, updating with the bottom-most node.

3. Final Answer:

   Hash Map (Dictionary) -> Option A

4. Quick Check:

   Use dictionary to map horizontal distance to node [OK]

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

Common Mistakes:

• Using stack which is LIFO and not suitable here
• Using queue alone without mapping distances
• Using linked list which is inefficient for key-value mapping

3. What is the bottom view output of the following binary tree?

        20
       /  \
     8     22
    / \      \
   5   3      25
      / \     
     10  14

medium

A. [5, 10, 3, 14, 25]

B. [5, 8, 10, 14, 25]

C. [5, 10, 3, 22, 25]

D. [8, 10, 3, 14, 22]

Solution

1. Step 1: Assign horizontal distances and find bottom nodes

   Horizontal distances: 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(-1), 14(1). Bottom nodes at each distance: -2:5, -1:10, 0:3, 1:14, 2:25.

2. Step 2: List bottom view nodes in order of horizontal distance

   From left to right: 5, 10, 3, 14, 25.

3. Final Answer:

   [5, 10, 3, 14, 25] -> Option A

4. Quick Check:

   Bottom view nodes by horizontal distance = [5,10,3,14,25] [OK]

Hint: Track horizontal distances and update bottom nodes [OK]

Common Mistakes:

• Not updating bottom node when a lower node appears
• Mixing horizontal distances order
• Including nodes not visible from bottom

4. Consider this code snippet to compute bottom view of a binary tree:

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

What is the main error in this code?

medium

A. Not checking if root is None

B. Using pop() removes last element, causing wrong traversal order

C. Not updating hd_node dictionary

D. Incorrect horizontal distance calculation

Solution

1. Step 1: Analyze queue usage and traversal order

   The code uses queue.pop() which removes last element (LIFO), making it behave like a stack, causing depth-first traversal instead of breadth-first.

2. Step 2: Understand impact on bottom view calculation

   Breadth-first traversal is needed to process nodes level by level to correctly update bottom nodes. Using pop() breaks this order.

3. Final Answer:

   Using pop() removes last element, causing wrong traversal order -> Option B

4. Quick Check:

   Use pop(0) or deque.popleft() for BFS [OK]

Hint: Use pop(0) for queue to maintain BFS order [OK]

Common Mistakes:

• Using pop() instead of pop(0) for queue
• Ignoring empty root check
• Incorrect horizontal distance updates

5. You have a binary tree where multiple nodes share the same horizontal distance and depth. How should you modify the bottom view algorithm to always show the node with the greatest depth at each horizontal distance?

hard

A. Store nodes in a list for each horizontal distance and pick the smallest value

B. Store only the first node encountered at each horizontal distance

C. Store both node value and depth in the dictionary, update only if new node depth is greater

D. Ignore depth and update dictionary with last visited node

Solution

1. Step 1: Understand the need to track depth

   To show the bottom-most node at each horizontal distance, we must know which node is deepest (greatest depth).

2. Step 2: Modify dictionary to store value and depth

   Store a tuple (node value, depth) for each horizontal distance. Update only if new node's depth is greater than stored depth.

3. Final Answer:

   Store both node value and depth in the dictionary, update only if new node depth is greater -> Option C

4. Quick Check:

   Track depth to update bottom view nodes correctly [OK]

Hint: Track depth with node to update bottom view correctly [OK]

Common Mistakes:

• Ignoring depth and overwriting nodes incorrectly
• Storing all nodes without filtering by depth
• Picking first or last node without depth check