Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Algorithm
3.
Implementation using Queue
4.
Implementation using HashMap()
5.
Frequently Asked Questions
5.1.
What is the bottom view of the tree?
5.2.
What is the top view of the binary tree?
5.3.
How do you display a binary tree?
5.4.
Is an empty tree a binary tree?
6.
Conclusion
Last Updated: Mar 27, 2024

Bottom View of a Binary Tree

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

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.

Illustration image

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

  1. Perform pre-order traversal to calculate the horizontal distance of each node.
  2. For each node:
    Add the node to the result if it is the first node to have a particular horizontal distance.
  3. 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 ComplexityO (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 ComplexityO (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.

Recommended Reading:

 

Recommended problems -

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Top View of A Binary Tree | Part-2
Next article
Check if Binary Tree Is BST or Not
Live masterclass