Bottom View of Binary Tree

Given a Binary Tree, print the bottom view from left to right. A node x is there in output if x is the bottom-most node at its horizontal distance from root.

Horizontal distance of left child of a node x is equal to horizontal distance of x minus 1, and that of right child is horizontal distance of x plus 1.

Solution:

• Traverse tree in level order and use sorted map to hold horizontal distance
• Or, Process in PreOrder and add node in sorted map based on horizontal distance and depth of node

Algorithm For 2nd Solution:

• Create a class to hold depth and node
• We need sorted map, key of this map would be horizontal distance and value would be above class
• When we are put in map, we’ll do in this way
  • If key not present in map, we just add new key and value
  • Else, if depth of current node is high than only we update in map.
• Traverse tree in PreOrder
  • If node is null then return
  • Add current node in sorted map with horizontal distance and depth
  • Recursively call left subtree with depth + 1 and horizontal distance – 1
  • Recursively call right subtree with depth + 1 and horizontal distance + 1

Latest Source Code:
Github: BottomViewOfBinaryTree.java

Output:

       20               
      / \       
     /   \      
    /     \     
   /       \    
   8       22       
  / \       \   
 /   \       \  
 5   3       25   
    / \         
    10 14         
                                

Bottom View: 5 10 3 14 25