Bottom View of a Binary Tree | Tree node class ; 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 , append ( ) 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
class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . hd = 1000000 NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def bottomView ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT hd = 0 NEW_LINE m = dict ( ) NEW_LINE q = [ ] NEW_LINE root . hd = hd NEW_LINE q . append ( root ) NEW_LINE while ( len ( q ) != 0 ) : NEW_LINE INDENT temp = q [ 0 ] NEW_LINE q . pop ( 0 ) NEW_LINE hd = temp . hd NEW_LINE m [ hd ] = temp . data NEW_LINE if ( temp . left != None ) : NEW_LINE INDENT temp . left . hd = hd - 1 NEW_LINE q . append ( temp . left ) NEW_LINE DEDENT if ( temp . right != None ) : NEW_LINE INDENT temp . right . hd = hd + 1 NEW_LINE q . append ( temp . right ) NEW_LINE DEDENT DEDENT for i in sorted ( m . keys ( ) ) : NEW_LINE INDENT print ( m [ i ] , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = Node ( 20 ) NEW_LINE root . left = Node ( 8 ) NEW_LINE root . right = Node ( 22 ) NEW_LINE root . left . left = Node ( 5 ) NEW_LINE root . left . right = Node ( 3 ) NEW_LINE root . right . left = Node ( 4 ) NEW_LINE root . right . right = Node ( 25 ) NEW_LINE root . left . right . left = Node ( 10 ) NEW_LINE root . left . right . right = Node ( 14 ) NEW_LINE print ( " Bottom ▁ view ▁ of ▁ the ▁ given ▁ binary ▁ tree ▁ : " ) NEW_LINE bottomView ( root ) NEW_LINE DEDENT