Bottom View of Binary Tree in DSA C#

Mental Model

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

Analogy: Imagine standing under a tree and looking up. The bottom view is like seeing only the leaves and branches that are directly above you, hiding the ones 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: root=20, left=8, right=22, 8's left=5, 8's right=3, 22's right=25, 3's left=10, 3's right=14

Goal: Find the bottom view nodes from left to right vertical lines

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

hd=0: 20
Tree: 20
/  \
8   22

Why: Root is the center vertical line

Step 2: Go left to 8 with hd = -1

hd=-1: 8, hd=0: 20
Tree:
   20
  /  \
 8   22

Why: Left child is one step left horizontally

Step 3: Go left to 5 with hd = -2

hd=-2: 5, hd=-1: 8, hd=0: 20
Tree:
    20
   /  \
  8   22
 /
5

Why: Left child again moves one step left

Step 4: Go right from 8 to 3 with hd = 0, replace 20 with 3 at hd=0 because 3 is lower

hd=-2: 5, hd=-1: 8, hd=0: 3
Tree:
    20
   /  \
  8   22
   \
    3

Why: 3 is lower than 20 at same vertical line, so bottom view updates

Step 5: Go left from 3 to 10 with hd = -1, replace 8 with 10 at hd=-1

hd=-2: 5, hd=-1: 10, hd=0: 3
Tree:
    20
   /  \
  8   22
   \
    3
   / 
  10

Why: 10 is lower than 8 at same vertical line, update bottom view

Step 6: Go right from 3 to 14 with hd = 1

hd=-2: 5, hd=-1: 10, hd=0: 3, hd=1: 14
Tree:
    20
   /  \
  8   22
   \
    3
   / \
  10 14

Why: New vertical line on right, add 14

Step 7: Go right from 22 to 25 with hd = 2

hd=-2: 5, hd=-1: 10, hd=0: 3, hd=1: 14, hd=2: 25
Tree:
    20
   /  \
  8   22
   \    \
    3    25
   / \
  10 14

Why: New vertical line further right, add 25

Result:

Bottom view nodes from left to right: 5 -> 10 -> 3 -> 14 -> 25

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Node {
    public int data;
    public Node left, right;
    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class BinaryTree {
    public Node root;

    public List<int> BottomView(Node root) {
        if (root == null) return new List<int>();

        // Map hd to node data
        Dictionary<int, int> hdNodeMap = new Dictionary<int, int>();
        // Queue stores node and its hd
        Queue<(Node node, int hd)> queue = new Queue<(Node, int)>();
        queue.Enqueue((root, 0));

        while (queue.Count > 0) {
            var (curr, hd) = queue.Dequeue();
            // Update map with current node at hd (bottommost)
            hdNodeMap[hd] = curr.data;

            if (curr.left != null) queue.Enqueue((curr.left, hd - 1));
            if (curr.right != null) queue.Enqueue((curr.right, hd + 1));
        }

        // Extract keys in sorted order
        List<int> keys = new List<int>(hdNodeMap.Keys);
        keys.Sort();

        List<int> bottomView = new List<int>();
        foreach (int key in keys) {
            bottomView.Add(hdNodeMap[key]);
        }
        return bottomView;
    }
}

class Program {
    static void Main() {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(20);
        tree.root.left = new Node(8);
        tree.root.right = new Node(22);
        tree.root.left.left = new Node(5);
        tree.root.left.right = new Node(3);
        tree.root.right.right = new Node(25);
        tree.root.left.right.left = new Node(10);
        tree.root.left.right.right = new Node(14);

        List<int> result = tree.BottomView(tree.root);
        Console.WriteLine(string.Join(" -> ", result));
    }
}

queue.Enqueue((root, 0));

Start BFS with root at horizontal distance 0

var (curr, hd) = queue.Dequeue();

Process next node and its horizontal distance

hdNodeMap[hd] = curr.data;

Update bottom view for this vertical line with current node

if (curr.left != null) queue.Enqueue((curr.left, hd - 1));

Add left child with hd one less

if (curr.right != null) queue.Enqueue((curr.right, hd + 1));

Add right child with hd one more

keys.Sort();

Sort vertical lines from left to right

foreach (int key in keys) { bottomView.Add(hdNodeMap[key]); }

Collect bottom view nodes in order

Output

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

Complexity Analysis

Time: O(n) because we visit each node once in BFS and insert/update map entries

Space: O(n) for the queue and map storing nodes and their horizontal distances

vs Alternative: Compared to recursive vertical traversal, BFS with map is simpler and efficient for bottom view

Edge Cases

Empty tree

Returns empty list with no nodes

DSA C#

if (root == null) return new List<int>();

Single node tree

Returns list with only root node

DSA C#

queue.Enqueue((root, 0));

Tree with all nodes on one side

Bottom view shows all nodes in a line

DSA C#

if (curr.left != null) queue.Enqueue((curr.left, hd - 1));

When to Use This Pattern

When asked to see nodes visible from the bottom of a tree, use BFS with horizontal distances to track and update the lowest nodes per vertical line.

Common Mistakes

Mistake: Not updating the node at a horizontal distance when a lower node appears
Fix: Always overwrite the map entry for hd with the current node during BFS to keep the bottommost node

Mistake: Using DFS which may not visit nodes level by level, missing bottom nodes
Fix: Use BFS to ensure nodes are processed level by level from top to bottom

Summary

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

Use it when you need to find the lowest nodes at each vertical line of the tree.

Track horizontal distances and update nodes level by level using BFS to get the bottom view.

Practice

1. What does the bottom view of a binary tree represent?

easy

A. The nodes visible when the tree is viewed from the right side

B. The nodes visible when the tree is viewed from the top

C. The nodes visible when the tree is viewed from the left side

D. The 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:

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

4. Quick Check:

   Bottom view = nodes visible 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 C# data structure is best suited to store nodes by their horizontal distance when computing the bottom view of a binary tree?

easy

A. Dictionary

B. List<int>

C. Stack<int>

D. Queue<int>

Solution

1. Step 1: Identify the need to map horizontal distance to node value

   We need a structure to store nodes keyed by their horizontal distance for quick updates and lookups.

2. Step 2: Choose the appropriate data structure

   A Dictionary allows mapping horizontal distance (int) to node value (int) efficiently.

3. Final Answer:

   Dictionary<int, int> -> Option A

4. Quick Check:

   Use Dictionary for horizontal distance mapping [OK]

Hint: Use Dictionary to map horizontal distance to node value [OK]

Common Mistakes:

• Using List which doesn't map keys to values
• Using Stack or Queue which are not key-value stores
• Confusing data structure roles

3. Consider the following binary tree:

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

What is the bottom view of this tree?

medium

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

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

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

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

Solution

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

   Assign horizontal distances (HD) starting from root (20) at HD=0: - 20(0), 8(-1), 22(1), 5(-2), 3(0), 25(2), 10(-1), 14(1) For each HD, the bottom-most node is: HD -2: 5 HD -1: 10 (overwrites 8) HD 0: 3 (overwrites 20) HD 1: 14 (overwrites 22) HD 2: 25

2. Step 2: Collect bottom view nodes in order of HD

   Order HD from left to right: -2, -1, 0, 1, 2 Bottom view nodes: [5, 10, 3, 14, 25]

3. Final Answer:

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

4. Quick Check:

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

Hint: Track horizontal distance and overwrite with lower nodes [OK]

Common Mistakes:

• Not updating nodes at same horizontal distance
• Confusing top view with bottom view
• Ignoring horizontal distance ordering

4. The following C# code attempts to compute the bottom view of a binary tree but has a bug. What is the error?

void BottomView(Node root) {
    if (root == null) return;
    var map = new Dictionary();
    var queue = new Queue<(Node node, int hd)>();
    queue.Enqueue((root, 0));
    while (queue.Count > 0) {
        var (node, hd) = queue.Dequeue();
        if (!map.ContainsKey(hd)) {
            map[hd] = node.data;
        }
        if (node.left != null) queue.Enqueue((node.left, hd - 1));
        if (node.right != null) queue.Enqueue((node.right, hd + 1));
    }
    foreach (var key in map.Keys.OrderBy(k => k)) {
        Console.Write(map[key] + " ");
    }
}

medium

A. It does not enqueue the root node

B. It only stores the first node at each horizontal distance, not the bottom-most

C. It uses a queue instead of a stack

D. It does not order the keys before printing

Solution

1. Step 1: Analyze how nodes are stored in the map

   The code adds node data to map only if the horizontal distance key is not present, so it keeps the first node encountered at that HD.

2. Step 2: Understand bottom view requires last node at each HD

   Bottom view needs the lowest node at each HD, so the map should update the value every time a node at the same HD is found, not only the first.

3. Final Answer:

   It only stores the first node at each horizontal distance, not the bottom-most -> Option B

4. Quick Check:

   Bottom view needs last node per HD, not first [OK]

Hint: Update map value for each node at HD to get bottom view [OK]

Common Mistakes:

• Using if (!map.ContainsKey) instead of always updating
• Ignoring horizontal distance updates
• Not ordering keys before printing (though code does)

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

hard

A. Store pairs of (node value, depth) in the map and update only if new node's depth is greater

B. Store only node values and update map only if node value is greater

C. Use a stack instead of a queue to traverse nodes

D. Ignore depth and just print nodes in level order

Solution

1. Step 1: Recognize the need to track depth with node values

   To ensure the bottom view shows the node with greatest depth at each horizontal distance, we must store depth along with node value.

2. Step 2: Update map only if new node's depth is greater

   When visiting a node, compare its depth with stored depth for that horizontal distance; update only if current node is deeper.

3. Final Answer:

   Store pairs of (node value, depth) in the map and update only if new node's depth is greater -> Option A

4. Quick Check:

   Track depth and update map for deeper nodes [OK]

Hint: Keep depth info and update map only if deeper node found [OK]

Common Mistakes:

• Ignoring depth and overwriting incorrectly
• Comparing node values instead of depths
• Changing traversal order without depth tracking