Related Tags

data structures
binary tree
bottom view

# How to print the bottom view of a binary tree Educative Answers Team

The bottom view of a binary tree refers to the bottommost nodes present at their horizontal distance.

For the nodes of a binary tree, the horizontal distance is defined as follows:

• Horizontal distance of the root = 0
• Horizontal distance of a ​left child = horizontal distance of its parent - 1
• Horizontal distance of a right child = horizontal distance of its parent + 1

The following illustration shows the horizontal distances and the bottom view of a binary tree.

Calculating the horizontal distances.
1 of 7

The bottom view for the tree in the illustration above is 4, 2, 6, 8, 7.

## Algorithm

1. Perform pre-order traversal to calculate the horizontal distance of each node.

2. For each node:

2.1. Add the node to the result if it is the first node to have a particular horizontal distance.

2.2 If a node exists in the result for a particular edit distance, then only replace that node with the present node if the present node is at a level greater than that of the already added node.

## Code

#include <iostream>
#include <vector>
#include <map>
using namespace std;
// A tree node
struct Tree
{
int data;
Tree *left;
Tree *right;
Tree(int data)
{
this -> data = data;
left = NULL;
right = NULL;
}
};
void bottomview(Tree * root, map<int,vector<int>>& m, int lev, int h_dist){
// Base case
if (root == NULL)
return;
// if the node is the first one with a specific horizontal
// distance, save its details.
if (m.find(h_dist) == m.end()) {
m[h_dist].push_back(lev);
m[h_dist].push_back(root -> data);
}
// Else, save the details if this node only if this node
// is at a greater level than the already saved node
else {
if (m[h_dist] <= lev) {
m[h_dist] = lev;
m[h_dist]= root -> data;
}
}
// Calling the function for the right and left subtrees
// with the appropriate parameters.
bottomview(root -> left, m, lev + 1, h_dist - 1);
bottomview(root -> right, m, lev + 1, h_dist + 1);
}
int main() {
// Creating a tree
Tree *root = new Tree(1);
root -> left = new Tree(2);
root -> right = new Tree(3);
root -> left -> left = new Tree(4);
root -> right -> left = new Tree(6);
root -> right -> right = new Tree(7);
root -> right -> left -> right = new Tree(8);
map<int,vector<int>> Map;
bottomview(root, Map, 1, 0);
for (auto it = Map.begin(); it != Map.end(); ++it)
{
cout << (it-> second)<< " ";
}
cout<<endl;
return 0;
}

RELATED TAGS

data structures
binary tree
bottom view 