In general, the bottom view of a binary tree is the nodes visible when viewed from the bottom.

Problem Statement: Given a Binary Tree, we need to print the bottom view from left to right. A node x is there in the output if x is the bottommost node at its horizontal distance. The horizontal distance of the left child of a node x is equal to a horizontal distance of x minus 1, and that of the right child is the horizontal distance of x plus 1.

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

The horizontal distance of the root = 0

The horizontal distance of a â€‹left child = horizontal distance of its parent - 1

The horizontal distance of a right child = horizontal distance of its parent + 1

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

The bottom view of the above binary tree is: 7 5 8 6

Note: In the order in which the values are stored in the Hashmap, we need to sort keys to print them in the right order.

Recommended: Try the Problem yourself before moving on to the solution.

Algorithm

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

For each node: Add the node to the result if it is the first node to have a particular horizontal distance.

If a node exists in the result for a particular horizontal 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.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Implementation using Queue

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][0] <= lev) {
m[h_dist][0] = lev;
m[h_dist][1]= 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)[1]<< " ";
}
cout<<endl;
return 0;
}

Output:

4 2 6 8 7

Time Complexity: O (n*log n): As we are using a map to store key-value pairs while traversing the binary tree, the time complexity of a single insertion being O(logn) in the map, the overall complexity becomes O(n*log n).

Space Complexity: The Space complexity is O(n): Storing the key-value pairs in a map corresponding to different horizontal distances contributes to space complexity.

Implementation using HashMap()

Algorithm

First, create a map-like map where the key is the horizontal distance and the value is a pair(a, b) where a is the value of the node and b is the height of the node.

Perform a pre-order traversal of the tree.

If the current node at a horizontal distance of h is the first weâ€™ve seen, insert it in the map.

Otherwise, compare the node with the existing one in the map and if the height of the new node is greater, update in the Map.

Code

#include <bits/stdc++.h>
#include <map>
using namespace std;
// Tree node class
struct Node
{
// data of the node
int data;
// horizontal distance of the node
int hd;
//left and right references
Node * left, * right;
// Constructor of tree node
Node(int key)
{
data = key;
hd = INT_MAX;
left = right = NULL;
}
};
void printBottomViewUtil(Node * root, int curr, int hd, map <int, pair <int, int>> & m)
{
// Base case
if (root == NULL)
return;
if (m.find(hd) == m.end())
{
m[hd] = make_pair(root -> data, curr);
}
else
{
pair < int, int > p = m[hd];
if (p.second <= curr)
{
m[hd].second = curr;
m[hd].first = root -> data;
}
}
// Recur for left subtree
printBottomViewUtil(root -> left, curr + 1, hd - 1, m);
// Recur for right subtree
printBottomViewUtil(root -> right, curr + 1, hd + 1, m);
}
void printBottomView(Node * root)
{
// Map to store Horizontal Distance,
// Height and Data.
map < int, pair < int, int > > m;
printBottomViewUtil(root, 0, 0, m);
// Prints the values stored by printBottomViewUtil()
map < int, pair < int, int > > ::iterator it;
for (it = m.begin(); it != m.end(); ++it)
{
pair < int, int > p = it -> second;
cout << p.first << " ";
}
}
int main()
{
Node * root = new Node(20);
root -> left = new Node(8);
root -> right = new Node(22);
root -> left -> left = new Node(5);
root -> left -> right = new Node(3);
root -> right -> left = new Node(4);
root -> right -> right = new Node(25);
root -> left -> right -> left = new Node(10);
root -> left -> right -> right = new Node(14);
printBottomView(root);
return 0;
}

Output

5 10 4 14 25

Time Complexity: O (n*log n): As we are using a map to store key-value pairs while traversing the binary tree, the time complexity of a single insertion being O(logn) in the map, the overall complexity becomes O(n*log n).

Space Complexity: O(n): Storing the key-value pairs in a map corresponding to different horizontal distances contributes to space complexity. Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What is the bottom view of the tree?

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.

What is the top view of the binary tree?

The top view of a binary tree is the set of nodes visible when the tree is viewed from the top. Given a binary tree, print the top view of it. The output nodes can be printed in any order. A node x is there in the output if x is the topmost node at its horizontal distance.

How do you display a binary tree?

You start traversing from the root, then go to the left node, then you again go to the left node until you reach a leaf node. At that point in time, you print the value of the node or mark it as visited and move to the right subtree. Continue the same algorithm until all nodes of the binary tree are visited.

Is an empty tree a binary tree?

The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

Conclusion

In this blog, we learned how to find the right view of a binary tree and how we can use different approaches to solve this problem.

In the first approach, we used a queue to implement the bottom view of a binary tree. The time complexity is O(N*log N) and the space complexity is O(N).

In the second approach, we used HashMap() to implement the bottom view of a binary tree. The time complexity is O(N*log N) and the space complexity is O(N).

If you want to learn about finding more information regarding the bottom view of a binary tree, we have a separate article that covers the approaches used to solve the problem. Do give it a read.