Bottom View of a Binary Tree

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

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;
}

You can also try this code with Online C++ Compiler

Run Code

Output

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.

Recommended Reading:

• Left View of Binary Tree
• Right View of Binary Tree
• Iterative Preorder Traversal of Binary Tree
• Top View of Binary Tree | Part 1
• Top View of BInary Tree | Part 2
• Top Trees Interview Questions

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree

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!