Bottom View of a Binary Tree | C ++ Program to print Bottom View of Binary Tree ; Tree node class ; data of the node ; horizontal distance of the node ; left and right references ; Constructor of tree node ; Method that prints the bottom view . ; Initialize a variable ' hd ' with 0 for the root element . ; TreeMap which stores key value pair sorted on key value ; Queue to store tree nodes in level order traversal ; Assign initialized horizontal distance value to root node and add it to the queue . ; In STL , push ( ) is used enqueue an item ; Loop until the queue is empty ( standard level order loop ) ; In STL , pop ( ) is used dequeue an item ; Extract the horizontal distance value from the dequeued tree node . ; Put the dequeued tree node to TreeMap having key as horizontal distance . Every time we find a node having same horizontal distance we need to replace the data in the map . ; If the dequeued node has a left child , add it to the queue with a horizontal distance hd - 1. ; If the dequeued node has a right child , add it to the queue with a horizontal distance hd + 1. ; Traverse the map elements using the iterator . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; int hd ; Node * left , * right ; Node ( int key ) { data = key ; hd = INT_MAX ; left = right = NULL ; } } ; void bottomView ( Node * root ) { if ( root == NULL ) return ; int hd = 0 ; map < int , int > m ; queue < Node * > q ; root -> hd = hd ; q . push ( root ) ; while ( ! q . empty ( ) ) { Node * temp = q . front ( ) ; q . pop ( ) ; hd = temp -> hd ; m [ hd ] = temp -> data ; if ( temp -> left != NULL ) { temp -> left -> hd = hd - 1 ; q . push ( temp -> left ) ; } if ( temp -> right != NULL ) { temp -> right -> hd = hd + 1 ; q . push ( temp -> right ) ; } } for ( auto i = m . begin ( ) ; i != m . end ( ) ; ++ i ) cout << i -> second << " ▁ " ; } 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 ) ; cout << " Bottom ▁ view ▁ of ▁ the ▁ given ▁ binary ▁ tree ▁ : STRNEWLINE " ; bottomView ( root ) ; return 0 ; }