Be the first user to complete this post

  • 0
 Add to List

Print the Bottom View of the Binary Tree.

Objec­tive: - Given a binary tree, print it in Bottom View of it.

What is Bottom View: Bottom view means when you look the tree from the bottom the nodes you will see will be called the bottom view of the tree. See the exam­ple below.

Bottom View of a Binary Tree

as you can see in the example above,8, 4, 9, 5, 3, 7 is the bottom view of the given binary tree.

Approach:

This Approach is quite sim­i­lar to the - Print the Binary Tree in Ver­ti­cal Order Path.
and Print The Top View of a Binary Tree. Just mod­i­fied the code so that it will print only the last ele­ment it will encounter in the ver­ti­cal order. That will be the bottom view.

How will you know that you are vis­it­ing the last node at every level(Vertically)?

  • Take a variable called level, whenever you go left, do level++ AND whenever you go right do level–.
  • With step above we have separated out the levels vertically.
level distribution
level distribution
  • Now you need to store the ele­ments of each level, so cre­ate a TreeMap and the (key,value) pair will be (level,element at that level).
  • Now all we need to do the level order tra­ver­sal and store only recent visited node at each level(vertically), this way you will be storing only the last element at each level.
  • We will use sim­ple queue tech­nique for level order tra­ver­sal or BFS.
  • we will cre­ate a class QueuePack, this will store the objects con­tain­ing node and its level.
  • At the end traverse through TreeMap and print all the values in it, it will be the bottom view of a tree.
  • See the code for bet­ter understanding.

    • Code:


    Output:

    :
4 6 5 7 8

    Also Read: