Trusted answers to developer questions
Trusted Answers to Developer Questions

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

RELATED TAGS

data structures
binary tree
bottom view
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring