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

Bottom View of Binary Tree

📖 Scenario: Imagine you have a tree of family members shown as a binary tree. You want to see which members are visible if you look at the tree from the bottom.

🎯 Goal: Build a program that finds the bottom view of a binary tree. The bottom view shows the nodes visible when the tree is seen from the bottom.

📋 What You'll Learn

Create a binary tree with given nodes and structure

Use a map to track horizontal distances of nodes

Traverse the tree to find the bottom view nodes

Print the bottom view nodes from left to right

💡 Why This Matters

🌍 Real World

Bottom view of a binary tree helps in visualizing hierarchical data from a different perspective, useful in network routing and geographical mapping.

💼 Career

Understanding tree traversals and views is important for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree Structure

Define a struct called Node with an int data, and two pointers left and right. Then create the root node with value 20, its left child with value 8, and right child with value 22.

DSA C++

// Define struct Node
// Create root node with data 20
// Create left child with data 8
// Create right child with data 22
// Your code here

Hint

Start by defining the node structure and then create the root and its two children exactly as described.

2

Add More Nodes to the Tree

Add the left child of node 8 with value 5 and the right child of node 8 with value 3. Also add the left child of node 22 with value 4 and the right child of node 22 with value 25.

DSA C++

root->left->left = new Node(5);
root->left->right = new Node(3);
root->right->left = new Node(4);
root->right->right = new Node(25);
// Your code here

Hint

Attach the new nodes exactly as children of the specified nodes.

3

Implement Bottom View Logic

Write a function void bottomView(Node* root) that uses a map<int, int> to store the bottom view nodes. Use a queue of pairs queue<pair<Node*, int>> to do a level order traversal. For each node, update the map with the node's data at its horizontal distance. Traverse the tree starting with horizontal distance 0 for root.

DSA C++

void bottomView(Node* root) {
    // Your code here
}

Hint

Use a queue to do level order traversal and a map to keep the latest node at each horizontal distance.

4

Print the Bottom View

Call the function bottomView(root) and print the bottom view nodes of the tree.

DSA C++

bottomView(root);
// Your code here

Hint

Call the bottomView function with the root node and print the result.