Bottom View of Binary Tree in DSA Python - Execution Trace

Concept Flow - Bottom View of Binary Tree

Start at root node

↓

Assign horizontal distance = 0

↓

Use queue for level order traversal

↓

For each node dequeued:

↓

Record node's value at its horizontal distance

↓

Enqueue left child with hd-1

↓

Enqueue right child with hd+1

↓

After traversal, extract values sorted by horizontal distance

↓

Print bottom view nodes left to right

Traverse the tree level by level, track horizontal distances, update bottom view map with latest node at each distance, then print sorted bottom view.

Execution Sample

DSA Python

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

def bottom_view(root):
    # Implementation here

This code sets up a binary tree node and outlines the bottom view function using level order traversal.

Execution Table

Step	Operation	Node Processed (val, hd)	Bottom View Map (hd: val)	Queue State (val, hd)	Visual State
1	Start with root	(20, 0)	{0: 20}	[(20, 0)]	20(0)
2	Dequeue node	(20, 0)	{0: 20}	[]	20(0)
3	Enqueue left child	(20, 0)	{0: 20}	[(8, -1)]	20(0) -> 8(-1)
4	Enqueue right child	(20, 0)	{0: 20}	[(8, -1), (22, 1)]	20(0) -> 8(-1), 22(1)
5	Dequeue node	(8, -1)	{0: 20, -1: 8}	[(22, 1)]	8(-1) -> 20(0) -> 22(1)
6	Enqueue left child	(8, -1)	{0: 20, -1: 8}	[(22, 1), (5, -2)]	8(-1) -> 20(0) -> 22(1), 5(-2)
7	Enqueue right child	(8, -1)	{0: 20, -1: 8}	[(22, 1), (5, -2), (3, 0)]	8(-1) -> 20(0) -> 22(1), 5(-2), 3(0)
8	Dequeue node	(22, 1)	{0: 20, -1: 8, 1: 22}	[(5, -2), (3, 0)]	8(-1) -> 20(0) -> 22(1), 5(-2), 3(0)
9	Enqueue right child	(22, 1)	{0: 20, -1: 8, 1: 22}	[(5, -2), (3, 0), (25, 2)]	8(-1) -> 20(0) -> 22(1), 5(-2), 3(0), 25(2)
10	Dequeue node	(5, -2)	{0: 20, -1: 8, 1: 22, -2: 5}	[(3, 0), (25, 2)]	5(-2) -> 8(-1) -> 20(0) -> 22(1), 3(0), 25(2)
11	Dequeue node	(3, 0)	{0: 3, -1: 8, 1: 22, -2: 5}	[(25, 2)]	5(-2) -> 8(-1) -> 3(0) -> 22(1), 25(2)
12	Enqueue left child	(3, 0)	{0: 3, -1: 8, 1: 22, -2: 5}	[(25, 2), (10, -1)]	5(-2) -> 8(-1) -> 3(0) -> 22(1), 25(2), 10(-1)
13	Enqueue right child	(3, 0)	{0: 3, -1: 8, 1: 22, -2: 5}	[(25, 2), (10, -1), (14, 1)]	5(-2) -> 8(-1) -> 3(0) -> 22(1), 25(2), 10(-1), 14(1)
14	Dequeue node	(25, 2)	{0: 3, -1: 8, 1: 22, -2: 5, 2: 25}	[(10, -1), (14, 1)]	5(-2) -> 8(-1) -> 3(0) -> 22(1) -> 25(2), 10(-1), 14(1)
15	Dequeue node	(10, -1)	{0: 3, -1: 10, 1: 22, -2: 5, 2: 25}	[(14, 1)]	5(-2) -> 10(-1) -> 3(0) -> 22(1) -> 25(2), 14(1)
16	Dequeue node	(14, 1)	{0: 3, -1: 10, 1: 14, -2: 5, 2: 25}	[]	5(-2) -> 10(-1) -> 3(0) -> 14(1) -> 25(2)
17	Traversal complete	N/A	{-2: 5, -1: 10, 0: 3, 1: 14, 2: 25}	[]	5(-2) -> 10(-1) -> 3(0) -> 14(1) -> 25(2)

💡 Queue empty, all nodes processed, bottom view map finalized

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	After 13	After 14	After 15	After 16	Final
Queue	[(20,0)]	[]	[(8,-1)]	[(8,-1), (22,1)]	[(22,1)]	[(22,1), (5,-2)]	[(22,1), (5,-2), (3,0)]	[(5,-2), (3,0)]	[(5,-2), (3,0), (25,2)]	[(3,0), (25,2)]	[(25,2)]	[(25,2), (10,-1)]	[(25,2), (10,-1), (14,1)]	[(10,-1), (14,1)]	[(14,1)]	[]	[]	[]
Bottom View Map	{}	{0:20}	{0:20, -1:8}	{0:20, -1:8}	{0:20, -1:8, 1:22}	{0:20, -1:8, 1:22, -2:5}	{0:20, -1:8, 1:22, -2:5}	{0:20, -1:8, 1:22, -2:5}	{0:20, -1:8, 1:22, -2:5, 2:25}	{0:20, -1:8, 1:22, -2:5, 2:25}	{0:3, -1:8, 1:22, -2:5, 2:25}	{0:3, -1:8, 1:22, -2:5, 2:25}	{0:3, -1:8, 1:22, -2:5, 2:25}	{0:3, -1:8, 1:22, -2:5, 2:25}	{0:3, -1:10, 1:22, -2:5, 2:25}	{0:3, -1:10, 1:14, -2:5, 2:25}	{0:3, -1:10, 1:14, -2:5, 2:25}	{-2:5, -1:10, 0:3, 1:14, 2:25}

Key Moments - 3 Insights

Why does the bottom view map update the value at a horizontal distance when a new node is processed?

Because the bottom view shows the lowest node at each horizontal distance, the map updates to the latest node encountered at that distance during level order traversal, as seen in steps 11, 15, and 16 where values at hd=0, -1, and 1 change.

Why do we use horizontal distance (hd) and how is it assigned?

Horizontal distance helps identify vertical columns in the tree. The root starts at hd=0, left child is hd-1, right child is hd+1. This is shown in the queue states where children have hd adjusted accordingly.

Why is level order traversal used instead of other traversals?

Level order ensures nodes are processed top to bottom, left to right, so the bottom-most node at each horizontal distance overwrites previous ones, correctly capturing the bottom view as shown in the queue processing steps.

Visual Quiz - 3 Questions

Look at the execution table, what is the bottom view map after processing node (3, 0) at step 11?

A {0: 3, -1: 8, 1: 22, -2: 5}

B {0: 20, -1: 8, 1: 22, -2: 5}

C {0: 3, -1: 10, 1: 22, -2: 5}

D {0: 3, -1: 8, 1: 14, -2: 5}

💡 Hint

Check the Bottom View Map column at step 11 in the execution table.

At which step does the horizontal distance -1 update from 8 to 10 in the bottom view map?

A Step 7

B Step 11

C Step 15

D Step 16

💡 Hint

Look for the Bottom View Map changes in the execution table rows around step 15.

If the node with value 3 had no children, how would the queue state change after step 13?

A Queue would be [(25, 2)] only

B Queue would be [(25, 2), (10, -1)]

C Queue would be [(25, 2), (14, 1)]

D Queue would be [(25, 2), (10, -1), (14, 1)]

💡 Hint

Check the enqueue operations at step 12 and 13 in the execution table.

Concept Snapshot

Bottom View of Binary Tree:
- Use level order traversal with a queue
- Track horizontal distance (hd) for each node
- Update map with node value at hd (latest overwrites)
- After traversal, sort map by hd and print values
- Shows nodes visible from bottom view
- Useful for visualizing tree vertical slices

Full Transcript

The bottom view of a binary tree shows the nodes visible when the tree is viewed from the bottom. We start at the root node with horizontal distance zero. Using a queue, we perform level order traversal. For each node, we record its value in a map keyed by horizontal distance, overwriting previous values at that distance. We enqueue left and right children with hd-1 and hd+1 respectively. After processing all nodes, we sort the map by horizontal distance and print the values. This approach ensures the bottom-most nodes at each vertical line are captured. The execution table traces each step, showing queue states, map updates, and the visual state of nodes with their horizontal distances. Key moments clarify why the map updates and why level order traversal is used. The visual quiz tests understanding of map updates and queue changes. This method helps visualize the tree's bottom view clearly.

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