Bottom View of Binary Tree in DSA C# - Build from Scratch

Bottom View of Binary Tree

📖 Scenario: You are working on a program that helps visualize a binary tree from different angles. One important view is the bottom view, which shows the nodes visible when looking at the tree from below.Imagine a tree of buildings where you want to see which buildings are visible from the street level looking up. The bottom view shows the last building you can see at each horizontal position.

🎯 Goal: Build a program that finds the bottom view of a binary tree. The bottom view contains the nodes that are visible when the tree is viewed from the bottom.You will create the tree, set up a helper variable, write the logic to find the bottom view, and then print the bottom view nodes in order.

📋 What You'll Learn

Create a binary tree with the exact nodes and structure given

Use a dictionary to track the bottom view nodes by their horizontal distance

Traverse the tree using a queue and track horizontal distances

Print the bottom view nodes from left to right

💡 Why This Matters

🌍 Real World

Bottom view of a binary tree helps in graphical visualizations, geographical mapping, and understanding hierarchical data from different perspectives.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, graphics, and spatial data processing.

1

Create the Binary Tree

Create a binary tree with the exact structure below using the Node class. The root node is root with value 20. Its left child is 8 and right child is 22. The left child of 8 is 5 and right child is 3. The left child of 3 is 10 and right child is 14. The right child of 22 is 25.

DSA C#

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

class Program
{
    static void Main(string[] args)
    {
        // Create the binary tree nodes and link them
        // Your code here
    }
}

Hint

Use the Node constructor to create each node and assign children using left and right properties.

2

Set Up the Dictionary for Bottom View

Create a dictionary called bottomViewMap of type Dictionary<int, int> to store the bottom view nodes. The key is the horizontal distance (int), and the value is the node's data (int). Initialize it as an empty dictionary.

DSA C#

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

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

        // Create the dictionary to hold bottom view nodes
        // Your code here
    }
}

Hint

Use Dictionary<int, int> and initialize it with new Dictionary<int, int>().

3

Implement Bottom View Logic

Write the logic to find the bottom view of the binary tree. Use a queue of tuples Queue<(Node node, int hd)> where hd is the horizontal distance. Start by enqueueing the root with horizontal distance 0. While the queue is not empty, dequeue an element, update bottomViewMap[hd] with the node's data (this overwrites previous nodes at the same horizontal distance), then enqueue the left child with hd - 1 and right child with hd + 1 if they exist.

DSA C#

using System;
using System.Collections.Generic;

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

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

        Dictionary bottomViewMap = new Dictionary();

        // Implement the bottom view traversal logic
        // Your code here
    }
}

Hint

Use a queue to do a level order traversal. Update the dictionary with the current node's data for each horizontal distance. Enqueue children with updated horizontal distances.

4

Print the Bottom View

Print the bottom view nodes in order from the smallest horizontal distance to the largest. Use foreach to iterate over the keys of bottomViewMap sorted in ascending order, and print the corresponding values separated by spaces.

DSA C#

using System;
using System.Collections.Generic;

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

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

        Dictionary bottomViewMap = new Dictionary();

        Queue queue = new Queue();
        queue.Enqueue((root, 0));

        while (queue.Count > 0)
        {
            var (node, hd) = queue.Dequeue();
            bottomViewMap[hd] = node.data;

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

        // Print the bottom view nodes in order
        // Your code here
    }
}

Hint

Sort the keys of bottomViewMap and print the values in that order separated by spaces.

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