Tree bottom view

#1

how to solve this problem

#2

@vivekpatel hey,The following are steps to print Bottom View of Binary Tree.

  1. We put tree nodes in a queue for the level order traversal.
  2. Start with the horizontal distance(hd) 0 of the root node, keep on adding left child to queue along with the horizontal distance as hd-1 and right child as hd+1.
  3. Also, use a TreeMap which stores key value pair sorted on key.
  4. Every time, we encounter a new horizontal distance or an existing horizontal distance put the node data for the horizontal distance as key. For the first time it will add to the map, next time it will replace the value. This will make sure that the bottom most element for that horizontal distance is present in the map and if you see the tree from beneath that you will see that element.
#3

Also, use a TreeMap which stores key value pair sorted on key.
what is TreeMap

#4

@vivekpatel hey tree map is imply a map with treenode as its key and value will be horizontal distance.

#5

I am not able to under get what you are saying please send me the algorithm

#6

@vivekpatel hey,Consider the case:
20 8 22 5 3 4 25 -1 -1 10 14 -1 -1 -1 -1 -1 -1 -1 -1

Expected Output:
5 10 4 14 25

Your Output:
5 10 4 22 25

With this example, check how you are going wrong with the code or logic.

Or follow this approach:
![WhatsApp Image 2019-08-20 at 18.24.35|666x500]
(upload://x9mzh14QU6p57VWnWBsNMlqe2c9.jpeg)
By maintaining a hashmap for horizontal distance of each node and by the BFS traversal you can solve this problem.

#7

I can’t open the image

#8

WhatsApp Image 2019-08-20 at 18.24.35
WhatsApp Image 2019-08-20 at 18.24.351280×960 88.3 KB

1 Like
#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.