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.
- 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:
20 / \ / \ / \ / \ 8 22 / \ \ / \ \ 5 3 25 / \ 10 14 Bottom View: 5 10 3 14 25