Bottom View of Binary Tree in DSA Python

Mental Model

We want to see the nodes visible if we look at the tree from the bottom. Each vertical line shows only the lowest node.

Analogy: Imagine standing under a tree and looking up. You only see the lowest leaves or branches directly above you, not the ones hidden behind.

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

Vertical lines: -2  -1   0   1   2
Nodes:          5   10  3  14  25

Dry Run Walkthrough

Input: Binary tree with nodes: 20 (root), 8 (left), 22 (right), 5 (left of 8), 3 (right of 8), 25 (right of 22), 10 (left of 3), 14 (right of 3)

Goal: Find the bottom view nodes of the tree, showing the lowest node at each vertical line

Step 1: Start at root 20 with horizontal distance (hd) = 0

hd=0: 20
Queue: [(20,0)]

Why: We assign root hd=0 to track vertical lines

Step 2: Visit node 20, update bottom view at hd=0 to 20, enqueue left child 8 (hd=-1) and right child 22 (hd=1)

Bottom view: {0:20}
Queue: [(8,-1), (22,1)]

Why: We record node 20 for hd=0 and prepare to visit children

Step 3: Visit node 8, update bottom view at hd=-1 to 8, enqueue left child 5 (hd=-2) and right child 3 (hd=0)

Bottom view: {-1:8, 0:20}
Queue: [(22,1), (5,-2), (3,0)]

Why: Node 8 is lowest so far at hd=-1; children added for next visits

Step 4: Visit node 22, update bottom view at hd=1 to 22, enqueue right child 25 (hd=2)

Bottom view: {-1:8, 0:20, 1:22}
Queue: [(5,-2), (3,0), (25,2)]

Why: Node 22 is lowest so far at hd=1; child 25 added

Step 5: Visit node 5, update bottom view at hd=-2 to 5, no children to enqueue

Bottom view: {-2:5, -1:8, 0:20, 1:22}
Queue: [(3,0), (25,2)]

Why: Node 5 is lowest at hd=-2; no children

Step 6: Visit node 3, update bottom view at hd=0 to 3 (overwrites 20), enqueue left child 10 (hd=-1) and right child 14 (hd=1)

Bottom view: {-2:5, -1:8, 0:3, 1:22}
Queue: [(25,2), (10,-1), (14,1)]

Why: Node 3 is lower than 20 at hd=0, so update; children added

Step 7: Visit node 25, update bottom view at hd=2 to 25, no children

Bottom view: {-2:5, -1:8, 0:3, 1:22, 2:25}
Queue: [(10,-1), (14,1)]

Why: Node 25 is lowest at hd=2

Step 8: Visit node 10, update bottom view at hd=-1 to 10 (overwrites 8), no children

Bottom view: {-2:5, -1:10, 0:3, 1:22, 2:25}
Queue: [(14,1)]

Why: Node 10 is lower than 8 at hd=-1

Step 9: Visit node 14, update bottom view at hd=1 to 14 (overwrites 22), no children

Bottom view: {-2:5, -1:10, 0:3, 1:14, 2:25}
Queue: []

Why: Node 14 is lower than 22 at hd=1

Result:

Bottom view nodes in order of hd: 5 -> 10 -> 3 -> 14 -> 25

Annotated Code

DSA Python

from collections import deque

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

def bottom_view(root):
    if not root:
        return []
    
    hd_node_map = dict()  # maps horizontal distance to node value
    queue = deque([(root, 0)])  # queue of pairs (node, horizontal distance)

    while queue:
        node, hd = queue.popleft()
        hd_node_map[hd] = node.val  # overwrite to keep bottom-most node

        if node.left:
            queue.append((node.left, hd - 1))  # left child hd = hd - 1
        if node.right:
            queue.append((node.right, hd + 1))  # right child hd = hd + 1

    # Extract bottom view nodes sorted by horizontal distance
    return [hd_node_map[hd] for hd in sorted(hd_node_map)]

# Driver code to test the example
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(5)
root.left.right = Node(3)
root.right.right = Node(25)
root.left.right.left = Node(10)
root.left.right.right = Node(14)

result = bottom_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 next node and its horizontal distance

hd_node_map[hd] = node.val

update bottom view map to keep the latest node at this horizontal distance

if node.left: queue.append((node.left, hd - 1))

enqueue left child with hd one less than current

if node.right: queue.append((node.right, hd + 1))

enqueue right child with hd one more than current

return [hd_node_map[hd] for hd in sorted(hd_node_map)]

return bottom view nodes sorted by horizontal distance

Output

5 -> 10 -> 3 -> 14 -> 25 -> null

Complexity Analysis

Time: O(n) because we visit each node once in level order traversal

Space: O(n) for the queue and the map storing nodes at each horizontal distance

vs Alternative: Compared to a naive approach that might do multiple traversals or store all nodes per vertical line, this approach is efficient with a single BFS and map update

Edge Cases

Empty tree (root is None)

Returns empty list as there are no nodes

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 depths

Bottom-most node overwrites previous nodes at that horizontal distance

DSA Python

hd_node_map[hd] = node.val

When to Use This Pattern

When asked to find nodes visible from the bottom of a binary tree, use a level order traversal with horizontal distances to track and overwrite nodes at each vertical line.

Common Mistakes

Mistake: Using preorder or inorder traversal which does not guarantee bottom-most nodes are processed last
Fix: Use level order traversal (BFS) to process nodes level by level ensuring bottom nodes overwrite top ones

Mistake: Not updating the map for nodes at the same horizontal distance, so top nodes remain instead of bottom
Fix: Always overwrite the map entry for a horizontal distance when visiting a node

Mistake: Not sorting the horizontal distances before output, resulting in unordered bottom view
Fix: Sort the keys of the map before collecting the bottom view nodes

Summary

Shows the lowest nodes visible when looking at a binary tree from the bottom.

Use when you need to find the bottom view of a tree, especially in visualization or tree projection problems.

Track horizontal distances and overwrite nodes during level order traversal to keep the bottom-most nodes.

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