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 perspectives. One useful view is the bottom view, which shows the nodes visible when the tree is seen from the bottom.Imagine standing under a tree and looking up. The bottom view shows the nodes that you would see directly above you, ignoring nodes hidden behind others.

🎯 Goal: Build a C program that finds and prints the bottom view of a given binary tree. The bottom view includes the nodes that are visible when the tree is viewed from the bottom.You will create the tree, set up a helper variable for horizontal distance, write the logic to find the bottom view, and finally print the bottom view nodes from left to right.

📋 What You'll Learn

Create a binary tree with the exact structure given

Use a variable to track horizontal distances of nodes

Implement the logic to find the bottom view using level order traversal

Print the bottom view nodes in order from left to right

💡 Why This Matters

🌍 Real World

Bottom view of a binary tree is useful in graphical representations, network routing visualizations, and understanding hierarchical data from different perspectives.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, algorithms, and systems involving hierarchical data.

1

Create the binary tree

Create the binary tree nodes with the exact structure below using struct Node and pointers. The tree structure is:

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

Create nodes with these values and link them exactly.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // Create the root node with data 20
    // Your code here
    return 0;
}

Hint

Use the newNode function to create each node and link them using left and right pointers.

2

Set up horizontal distance tracking

Declare an integer variable called hd and initialize it to 0. This variable will help track the horizontal distance of nodes from the root during traversal.

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    struct 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);

    // Declare an integer variable hd and set it to 0
    // Your code here
    return 0;
}

Hint

Simply declare int hd = 0; inside main.

3

Implement bottom view logic

Write a function called bottomView that takes the root node pointer as input and prints the bottom view of the binary tree. Use a level order traversal with a queue and a map (or array) to track the last node at each horizontal distance. Update the map with the current node's data at each horizontal distance. Use a queue of pairs (node pointer and horizontal distance).

DSA C

#include 
#include 

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Implement the bottomView function here

int main() {
    struct 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);

    int hd = 0;

    // Call bottomView with root
    // Your code here

    return 0;
}

Hint

Use a queue to do level order traversal. Track horizontal distances and update the bottom view array with the latest node at each horizontal distance.

4

Print the bottom view

In the main function, call the bottomView function with the root node to print the bottom view of the binary tree.

DSA C

#include 
#include 

// ... previous code ...

int main() {
    struct 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);

    int hd = 0;

    // Call bottomView with root
    // Your code here

    return 0;
}

Hint

Call bottomView(root); inside main to print the bottom view.

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