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 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
View all Courses