# Print the Bottom View of the Binary Tree.

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

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

Bottom-View-of-a-Binary-Tree

as you can see in the exam­ple above,8, 4, 9, 5, 3, 7 is the bot­tom 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 bot­tom view.

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

• Take a vari­able called level, when­ever you go left, do level++ AND when­ever you go right do level–.
• With step above we have sep­a­rated out the lev­els vertically.
• level dis­tri­b­u­tion

• 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 vis­ited node at each level(vertically), this way you will be stor­ing only the last ele­ment 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 tra­verse through TreeMap and print all the val­ues in it, it will be the bot­tom view of a tree.
• See the code for bet­ter understanding.

Code:

```Output:
4 6 5 7 8
```

#### You may also like...

• Xiaozhen Zhong

how would the tpre-order tra­verse guar­an­tee most recent vis­ited node would be at “bot­tom” of a ver­ti­cal level?
Would fol­low­ing sequence work?
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.left.right.left = new Node(6);
root.left.right.right = new Node(7);
root.left.right.right.right = new Node(9); ==> add another right node, which will be at same ver­ti­cal level of node(8) but lower.
root.right.right = new Node(8);
We should get 4 6 5 7 9 as bot­tom view, but my guess is the code will return 4 6 5 7 8 (wrong result)

• tuto­ri­al­hori­zon

Hi Xiaozhen,

Code is cor­rect and will return 4 6 5 7 9, don’t con­cen­trate on pre­order tra­ver­sal, we are stor­ing the node at each ver­ti­cal level in a hash map ( in fact we are updat­ing it so hash map will con­tain the last node vis­ited at that level) See the diagram.

• http://www.waytocrack.com kumar
• Sub­odh Karwa

Can you please explain how 5 and 6 both being at level –0 are printed using the code ?

• suvro

Print In-Order nodes where either left or right child is NULL

pri­vate sta­tic void printBottomView(Tree tree) {

if(tree==null)
return;
printBottomView(tree.leftChild);
if(tree.leftChild==null||tree.rightChild==null)
System.out.println(“===”+tree.data+”===”);
printBottomView(tree.rightChild);
}