Bottom View of Binary Tree in DSA C# - Deep Dive

Overview - Bottom View of Binary Tree

What is it?

The bottom view of a binary tree shows the nodes visible when the tree is seen from below. It means we look at the tree from the bottom and note the nodes that appear in the vertical lines. Each vertical line shows only one node, the one closest to the bottom. This helps us understand the structure of the tree from a different angle.

Why it matters

Without the bottom view, we miss how nodes overlap vertically in a tree and which nodes are actually visible from below. This view helps in problems like terrain mapping, network routing, or visualizing hierarchical data from different perspectives. It solves the problem of identifying the lowest visible nodes in each vertical slice of the tree.

Where it fits

Before learning bottom view, you should understand binary trees, tree traversal methods, and the concept of horizontal distance in trees. After this, you can explore related views like top view, left view, and right view of binary trees, and then move on to more complex tree problems like vertical order traversal.

Mental Model

Core Idea

The bottom view of a binary tree is the set of nodes visible when looking up from the bottom, showing the lowest node at each vertical position.

Think of it like...

Imagine standing under a tree and looking up through the branches. The bottom view is like seeing the leaves and branches that block your view from below, showing only the lowest leaf or branch at each horizontal position.

       (Root)
         1
       /   \
      2     3
     / \   / \
    4   5 6   7

Horizontal distances:
Node 4: -2 | Node 2: -1 | Node 1: 0 | Node 3: 1 | Node 7: 2
Bottom view nodes: 4 -> 2 -> 6 -> 3 -> 7

Build-Up - 6 Steps

1

Foundation

Understanding Binary Trees Basics

Concept: Learn what a binary tree is and how nodes connect with left and right children.

A binary tree is a structure where each node has up to two children: left and right. The top node is called the root. Each child can have its own children, forming a tree shape. For example, node 1 can have node 2 as left child and node 3 as right child.

Result

You can visualize and represent a binary tree with nodes connected by left and right links.

Understanding the basic structure of binary trees is essential before exploring views like bottom view, which depend on node positions.

2

Foundation

Horizontal Distance Concept in Trees

Concept: Introduce horizontal distance (HD) to locate nodes vertically in the tree.

Assign horizontal distance 0 to the root. For left child, HD = parent's HD - 1. For right child, HD = parent's HD + 1. This helps group nodes vertically. For example, root 1 has HD 0, left child 2 has HD -1, right child 3 has HD +1.

Result

Each node has a horizontal distance value that helps identify its vertical line in the tree.

Knowing horizontal distance lets us group nodes by vertical lines, which is key to finding bottom view nodes.

3

Intermediate

Tracking Nodes by Horizontal Distance

🤔Before reading on: Do you think the bottom view shows the topmost or bottommost node at each horizontal distance? Commit to your answer.

Concept: Use horizontal distance to track nodes and update the bottommost node at each vertical line.

Traverse the tree level by level (breadth-first). For each node, record its horizontal distance and depth (level). Keep updating the node stored for each horizontal distance if the current node is at a deeper level. This way, the last updated node at each horizontal distance is the bottom view node.

Result

You get a map of horizontal distances to the bottommost nodes visible from below.

Understanding that bottom view depends on the deepest node at each horizontal distance clarifies why level order traversal is used.

4

Intermediate

Implementing Bottom View with Queue and Map

🤔Before reading on: Will a depth-first or breadth-first traversal better capture the bottom view nodes? Commit to your answer.

Concept: Use a queue for level order traversal and a map to store nodes by horizontal distance.

Initialize a queue with root node and HD=0. While queue not empty, dequeue node, update map[HD] = node's value (overwriting previous). Enqueue left child with HD-1, right child with HD+1. After traversal, map contains bottom view nodes.

Result

A map with horizontal distances as keys and bottom view node values as values.

Using breadth-first traversal ensures nodes at lower levels overwrite higher ones, capturing the bottom view correctly.

5

Advanced

C# Code for Bottom View of Binary Tree

🤔Before reading on: Predict the output bottom view for the example tree after running the code. Commit to your answer.

Concept: Implement the bottom view algorithm in C# using a queue and dictionary.

public class Node { public int Data; public Node Left, Right; public Node(int data) { Data = data; Left = Right = null; } } public static void BottomView(Node root) { if (root == null) return; var queue = new Queue<(Node node, int hd)>(); var map = new SortedDictionary(); queue.Enqueue((root, 0)); while (queue.Count > 0) { var (node, hd) = queue.Dequeue(); map[hd] = node.Data; // overwrite to keep bottommost if (node.Left != null) queue.Enqueue((node.Left, hd - 1)); if (node.Right != null) queue.Enqueue((node.Right, hd + 1)); } foreach (var val in map.Values) { Console.Write(val + " -> "); } Console.WriteLine("null"); } // Example tree creation and call // Node root = new Node(1); // root.Left = new Node(2); // root.Right = new Node(3); // root.Left.Left = new Node(4); // root.Left.Right = new Node(5); // root.Right.Left = new Node(6); // root.Right.Right = new Node(7); // BottomView(root);

Result

4 -> 2 -> 6 -> 3 -> 7 -> null

Seeing the full code connects the theory to practice and shows how data structures like queue and dictionary work together to solve the problem.

6

Expert

Handling Edge Cases and Optimizations

🤔Before reading on: Do you think nodes at the same horizontal distance but different depths always appear in bottom view? Commit to your answer.

Concept: Consider trees with multiple nodes at same horizontal distance and depth, and optimize space/time.

If two nodes share the same horizontal distance and depth, the one visited last in level order is chosen. To optimize, use a dictionary with horizontal distance keys and store (node value, depth). Update only if new node depth >= stored depth. Also, use SortedDictionary to keep keys sorted for output. For large trees, consider iterative traversal to avoid stack overflow.

Result

Robust bottom view that handles ties and large inputs efficiently.

Knowing how to handle ties and optimize traversal prevents bugs and improves performance in real-world applications.

Under the Hood

The algorithm uses a breadth-first traversal to visit nodes level by level, tracking each node's horizontal distance from the root. A map stores the latest node value for each horizontal distance, effectively overwriting nodes higher up with nodes lower down. This works because level order traversal visits nodes top-down, left to right, ensuring the bottommost node at each horizontal distance is the last stored.

Why designed this way?

This approach was chosen because vertical lines in a tree correspond to horizontal distances, and the bottom view requires the lowest node per vertical line. Level order traversal naturally processes nodes by depth, making it easy to overwrite nodes at the same horizontal distance with deeper ones. Alternatives like depth-first traversal would require more complex tracking and might miss the correct bottommost nodes.

┌───────────────┐
│   Start Root  │
│ HD = 0       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Enqueue root  │
│ with HD=0     │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ While queue not empty:       │
│  Dequeue node and HD        │
│  Update map[HD] = node.val  │
│  Enqueue left child HD-1    │
│  Enqueue right child HD+1   │
└─────────────┬───────────────┘
              │
              ▼
┌─────────────────────────────┐
│ After traversal, map holds  │
│ bottom view nodes by HD     │
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does the bottom view show the topmost node at each vertical line? Commit yes or no.

Common Belief: The bottom view shows the topmost node visible from below at each vertical line.

Reality: The bottom view actually shows the lowest (deepest) node at each vertical line, not the topmost.

Why it matters: Confusing top and bottom views leads to wrong answers and misunderstandings of tree structure.

Quick: Can depth-first traversal alone correctly find the bottom view? Commit yes or no.

Common Belief: Depth-first traversal is enough to find the bottom view nodes.

Reality: Depth-first traversal alone can miss nodes because it doesn't process nodes level by level, so it may not overwrite higher nodes with lower ones correctly.

Why it matters: Using the wrong traversal causes incorrect bottom view results, especially in unbalanced trees.

Quick: If two nodes share the same horizontal distance and depth, does the first visited node always appear in bottom view? Commit yes or no.

Common Belief: The first visited node at a horizontal distance and depth is always in the bottom view.

Reality: The last visited node at that horizontal distance and depth overwrites the previous one in bottom view.

Why it matters: Ignoring this can cause subtle bugs where the wrong node is shown in the bottom view.

Expert Zone

1

The bottom view depends on horizontal distance and depth, but ties at the same depth are resolved by visit order in level order traversal.

2

Using a SortedDictionary in C# ensures the bottom view nodes are output in left-to-right order without extra sorting steps.

3

In very large trees, iterative level order traversal avoids stack overflow risks that recursive methods might cause.

When NOT to use

Bottom view is not suitable when you need all nodes visible from the side or top; use top view or vertical order traversal instead. For weighted or non-binary trees, specialized algorithms are needed.

Production Patterns

Bottom view is used in visualization tools to display hierarchical data from different perspectives, in network routing to find lowest nodes in layered graphs, and in terrain mapping where lowest visible points matter.

Connections

Top View of Binary Tree

Opposite vertical perspective of the same tree structure.

Understanding bottom view clarifies top view by showing how node visibility changes when looking from above versus below.

Breadth-First Search (BFS)

Bottom view algorithm relies on BFS traversal to process nodes level by level.

Knowing BFS deeply helps understand why bottom view captures the lowest nodes correctly and how traversal order affects results.

Geographical Terrain Mapping

Both involve identifying visible points from a viewpoint considering vertical and horizontal positions.

Seeing bottom view as a form of terrain visibility helps apply similar logic in mapping and visualization fields.

Common Pitfalls

#1 Using depth-first traversal without tracking depth properly.

Wrong approach:

void BottomViewDFS(Node node, int hd, int depth, Dictionary map) {
if (node == null) return;
if (!map.ContainsKey(hd) || map[hd].dep <= depth) {
map[hd] = (node.Data, depth);
}
BottomViewDFS(node.Left, hd - 1, depth + 1, map);
BottomViewDFS(node.Right, hd + 1, depth + 1, map);
}
// Called with BottomViewDFS(root, 0, 0, map);

Correct approach:

Use level order traversal with a queue to ensure nodes are processed by depth:

Queue<(Node node, int hd)> queue = new Queue<(Node, int)>();
queue.Enqueue((root, 0));
while(queue.Count > 0) {
var (node, hd) = queue.Dequeue();
map[hd] = node.Data; // overwrite
if(node.Left != null) queue.Enqueue((node.Left, hd - 1));
if(node.Right != null) queue.Enqueue((node.Right, hd + 1));
}

Root cause:

Depth-first traversal visits nodes in a path-first manner, missing the correct order to overwrite nodes at the same horizontal distance and depth.

#2 Not sorting the horizontal distances before output.

Wrong approach:

foreach(var val in map.Values) {
Console.Write(val + " -> ");
}
Console.WriteLine("null");

Correct approach:

Use a SortedDictionary for map so keys are sorted automatically, or sort keys before output:

foreach(var key in map.Keys.OrderBy(k => k)) {
Console.Write(map[key] + " -> ");
}
Console.WriteLine("null");

Root cause:

Dictionary keys are unordered, so output without sorting leads to incorrect left-to-right bottom view order.

Key Takeaways

Bottom view of a binary tree shows the lowest node visible at each vertical line when looking from below.

Horizontal distance is key to grouping nodes vertically and finding their bottom view positions.

Breadth-first traversal ensures nodes are processed by depth, allowing correct overwriting of nodes in bottom view.

Using a map keyed by horizontal distance and updating with the deepest node value captures the bottom view efficiently.

Handling edge cases like ties and sorting output keys ensures accurate and ordered bottom view results.

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