Bottom View of a Binary Tree | Java 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 ; Tree class ; root node of tree ; Default constructor ; Parameterized tree constructor ; 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 ) ; 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. ; Extract the entries of map into a set to traverse an iterator over that . ; Make an iterator ; Traverse the map elements using the iterator . ; Main driver class
import java . util . * ; import java . util . Map . Entry ; class Node { int data ; int hd ; Node left , right ; public Node ( int key ) { data = key ; hd = Integer . MAX_VALUE ; left = right = null ; } } class Tree { Node root ; public Tree ( ) { } public Tree ( Node node ) { root = node ; } public void bottomView ( ) { if ( root == null ) return ; int hd = 0 ; Map < Integer , Integer > map = new TreeMap < > ( ) ; Queue < Node > queue = new LinkedList < Node > ( ) ; root . hd = hd ; queue . add ( root ) ; while ( ! queue . isEmpty ( ) ) { Node temp = queue . remove ( ) ; hd = temp . hd ; map . put ( hd , temp . data ) ; if ( temp . left != null ) { temp . left . hd = hd - 1 ; queue . add ( temp . left ) ; } if ( temp . right != null ) { temp . right . hd = hd + 1 ; queue . add ( temp . right ) ; } } Set < Entry < Integer , Integer > > set = map . entrySet ( ) ; Iterator < Entry < Integer , Integer > > iterator = set . iterator ( ) ; while ( iterator . hasNext ( ) ) { Map . Entry < Integer , Integer > me = iterator . next ( ) ; System . out . print ( me . getValue ( ) + " ▁ " ) ; } } } public class BottomView { public static void main ( String [ ] args ) { 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 ) ; Tree tree = new Tree ( root ) ; System . out . println ( " Bottom ▁ view ▁ of ▁ the ▁ given ▁ binary ▁ tree : " ) ; tree . bottomView ( ) ; } }