Bottom View of Binary Tree

Bottom View of Binary Tree

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
```
Author: