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:
The following illustration shows the horizontal distances and the bottom view of a binary tree.
The bottom view for the tree in the illustration above is 4, 2, 6, 8, 7.
Perform pre-order traversal to calculate the horizontal distance of each node.
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.
#include <iostream>#include <vector>#include <map>using namespace std;// A tree nodestruct 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 caseif (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 nodeelse {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 treeTree *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;}
Free Resources