### 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