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 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: 20 / \ 8 22 / \ \ 5 3 25 / \ 10 14

Goal: Find the bottom view nodes: the lowest nodes visible from bottom for each vertical line

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

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

Why: We begin BFS from root at hd 0 to track vertical lines

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

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

Why: 20 is the first node at hd 0, so bottom view at 0 is 20

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

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

Why: 8 is lowest at hd -1 so far; 3 at hd 0 may replace 20 later

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

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

Why: 22 is lowest at hd 1 so far

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

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

Why: 5 is lowest at hd -2

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

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

Why: 3 is lower than 20 at hd 0, so replace 20

Step 7: Visit 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: 25 is lowest at hd 2

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

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

Why: 10 is lower than 8 at hd -1, so replace 8

Step 9: Visit 14, update bottom view at hd=1 to 14, no children

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

Why: 14 is lower than 22 at hd 1, so replace 22

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Node structure for binary tree
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Queue node for BFS storing tree node and horizontal distance
typedef struct QNode {
    Node* treeNode;
    int hd;
    struct QNode* next;
} QNode;

// Queue structure
typedef struct Queue {
    QNode *front, *rear;
} Queue;

// Create new tree node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Create empty queue
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// Enqueue tree node with hd
void enqueue(Queue* q, Node* node, int hd) {
    QNode* temp = (QNode*)malloc(sizeof(QNode));
    temp->treeNode = node;
    temp->hd = hd;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

// Dequeue returns QNode*
QNode* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    QNode* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    return temp;
}

// Map structure for hd to node data
// Using fixed size array for simplicity, hd range assumed [-1000,1000]
#define OFFSET 1000
#define MAX_SIZE 2001

int bottomView(Node* root) {
    if (!root) return 0;

    int hdNode[MAX_SIZE];
    int visited[MAX_SIZE];
    for (int i = 0; i < MAX_SIZE; i++) {
        visited[i] = 0; // mark hd as not visited
    }

    Queue* q = createQueue();
    enqueue(q, root, 0); // root hd=0

    int minHd = 0, maxHd = 0;

    while (q->front != NULL) {
        QNode* curr = dequeue(q);
        Node* node = curr->treeNode;
        int hd = curr->hd;
        free(curr);

        // Update bottom view for hd
        hdNode[hd + OFFSET] = node->data;
        visited[hd + OFFSET] = 1;

        if (hd < minHd) minHd = hd;
        if (hd > maxHd) maxHd = hd;

        if (node->left) enqueue(q, node->left, hd - 1);
        if (node->right) enqueue(q, node->right, hd + 1);
    }

    // Print bottom view from minHd to maxHd
    for (int i = minHd; i <= maxHd; i++) {
        if (visited[i + OFFSET]) {
            printf("%d", hdNode[i + OFFSET]);
            if (i != maxHd) printf(" -> ");
        }
    }
    printf(" -> null\n");
    return 1;
}

int main() {
    /* Construct the tree:
           20
          /  \
        8     22
       / \      \
      5   3      25
         / \     
        10  14   
    */
    Node* root = newNode(20);
    root->left = newNode(8);
    root->right = newNode(22);
    root->left->left = newNode(5);
    root->left->right = newNode(3);
    root->right->right = newNode(25);
    root->left->right->left = newNode(10);
    root->left->right->right = newNode(14);

    bottomView(root);
    return 0;
}

enqueue(q, root, 0);

Start BFS from root with horizontal distance 0

QNode* curr = dequeue(q);

Remove front node from queue to process

hdNode[hd + OFFSET] = node->data; visited[hd + OFFSET] = 1;

Update bottom view for current horizontal distance with latest node

if (node->left) enqueue(q, node->left, hd - 1);

Add left child with hd one less

if (node->right) enqueue(q, node->right, hd + 1);

Add right child with hd one more

for (int i = minHd; i <= maxHd; i++) { if (visited[i + OFFSET]) printf(...); }

Print bottom view nodes from leftmost to rightmost vertical line

Output

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

Complexity Analysis

Time: O(n) because we visit each node once during BFS

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

vs Alternative: Naive approach might do multiple traversals or store all nodes per vertical line increasing complexity

Edge Cases

Empty tree

No output, function returns immediately

DSA C

if (!root) return 0;

Single node tree

Bottom view is just that node

DSA C

enqueue(q, root, 0);

All nodes on left side

Bottom view shows all nodes with decreasing hd

DSA C

if (node->left) enqueue(q, node->left, hd - 1);

When to Use This Pattern

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

Common Mistakes

Mistake: Using DFS instead of BFS causing incorrect bottom nodes because deeper nodes may be missed
Fix: Use BFS to process nodes level by level ensuring bottom nodes overwrite upper ones

Mistake: Not updating bottom view when a node at same horizontal distance but lower level appears
Fix: Always overwrite bottom view entry for a horizontal distance when visiting a node

Summary

Finds the lowest nodes visible from bottom for each vertical line in a binary tree.

Use when you want to see the tree from below, showing only the bottom-most nodes per vertical line.

Track horizontal distances during BFS and update bottom view with the latest node at each distance.

Practice

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

easy

A. Nodes visible when the tree is viewed from the bottom

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 right side

Solution

1. Step 1: Understand the bottom view concept

   The bottom view shows nodes that are visible when looking at the tree from below, ignoring nodes hidden behind others.

2. Step 2: Compare with other views

   Top, left, and right views show nodes from different angles, but bottom view specifically shows the lowest nodes at each horizontal distance.

3. Final Answer:

   Nodes visible when the tree is viewed from the bottom -> Option A

4. Quick Check:

   Bottom view = nodes visible from below [OK]

Hint: Bottom view shows lowest nodes at each horizontal position [OK]

Common Mistakes:

• Confusing bottom view with top view
• Thinking it shows all leaf nodes only
• Mixing bottom view with side views

2. Which data structure is commonly used to track nodes and their horizontal distances for bottom view calculation?

easy

A. Stack

B. Hash Map (Dictionary)

C. Linked List

D. Queue

Solution

1. Step 1: Identify the need for horizontal distance mapping

   To find the bottom view, we map each node's horizontal distance to its value, updating with the lowest node at that distance.

2. Step 2: Choose the suitable data structure

   A hash map (dictionary) stores horizontal distance as key and node value as value, allowing quick updates and lookups.

3. Final Answer:

   Hash Map (Dictionary) -> Option B

4. Quick Check:

   Use hash map to map horizontal distance to node [OK]

Hint: Use hash map to store horizontal distance and node value [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 lookups

3. What is the bottom view output of this binary tree?

        1
       / \
      2   3
       \   \
        4   5
         \   \
          6   7

Options show node values from left to right in bottom view.

medium

A. [2, 4, 6, 7]

B. [2, 4, 6, 3, 7]

C. [2, 4, 6, 5, 7]

D. [1, 2, 4, 6, 7]

Solution

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

   Assign horizontal distances: 1=0, 2=-1, 3=1, 4=0, 5=2, 6=1, 7=3. Bottom nodes at each distance are: -1:2, 0:4, 1:6, 2:5, 3:7.

2. Step 2: Collect bottom view nodes from left to right

   From leftmost (-1) to rightmost (3), nodes are 2, 4, 6, 5, 7.

3. Final Answer:

   [2, 4, 6, 5, 7] -> Option C

4. Quick Check:

   Bottom view nodes left to right = [2, 4, 6, 5, 7] [OK]

Hint: Track horizontal distances and pick last node at each [OK]

Common Mistakes:

• Including nodes not visible from bottom
• Confusing horizontal distances
• Listing nodes in wrong order

4. Identify the error in this C code snippet for bottom view calculation:

void bottomView(Node* root) {
    map hdNodeMap;
    queue> q;
    q.push({root, 0});
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        Node* node = p.first;
        int hd = p.second;
        if (hdNodeMap.find(hd) == hdNodeMap.end()) {
            hdNodeMap[hd] = node->data;
        }
        if (node->left) q.push({node->left, hd - 1});
        if (node->right) q.push({node->right, hd + 1});
    }
    for (auto it : hdNodeMap) {
        cout << it.second << " ";
    }
}

medium

A. Output loop should print keys instead of values

B. Queue is not initialized properly

C. Left and right child checks are reversed

D. Using map prevents updating bottom nodes at same horizontal distance

Solution

1. Step 1: Analyze map usage for horizontal distances

   The code inserts node data only if horizontal distance is not present, so it keeps the first node seen, which is top view behavior.

2. Step 2: Correct approach for bottom view

   For bottom view, update the map every time a node at the same horizontal distance is found, so the last node at that distance remains.

3. Final Answer:

   Using map prevents updating bottom nodes at same horizontal distance -> Option D

4. Quick Check:

   Bottom view needs updating map entries [OK]

Hint: Update map for every node at horizontal distance for bottom view [OK]

Common Mistakes:

• Using if condition to insert only once (top view logic)
• Not updating map with lower nodes
• Confusing top and bottom view logic

5. Given a binary tree where multiple nodes share the same horizontal distance and level, how should the bottom view algorithm decide which node to show?

hard

A. Show the node that appears last in level order traversal at that horizontal distance

B. Show the node that appears first in level order traversal at that horizontal distance

C. Show the node with the smallest value at that horizontal distance

D. Show the node with the largest value at that horizontal distance

Solution

1. Step 1: Understand node conflicts at same horizontal distance and level

   When nodes share horizontal distance and level, bottom view shows the one visible from bottom, which is the last node encountered in level order at that position.

2. Step 2: Use level order traversal order to decide

   Level order traversal visits nodes top to bottom, left to right. The last node at a horizontal distance overwrites previous ones in the map.

3. Final Answer:

   Show the node that appears last in level order traversal at that horizontal distance -> Option A

4. Quick Check:

   Bottom view picks last node at horizontal distance [OK]

Hint: Last node at horizontal distance in level order is bottom view node [OK]

Common Mistakes:

• Picking first node instead of last
• Choosing node by value instead of position
• Ignoring traversal order impact