# 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. 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.
• 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:

 import java.util.LinkedList; import java.util.Queue; import java.util.Set; import java.util.TreeMap; public class BottomViewOfBT { public static TreeMap ht = new TreeMap<>();; public static void bottomView(Node root, int level) { if (root == null) return; // create a queue for level order traversal Queue queue = new LinkedList<>(); // add root with level 0 (create a queue item pack) queue.add(new QueuePack(level, root)); while (!queue.isEmpty()) { QueuePack q = queue.remove(); // take out the items from the package Node tnode = q.tnode; int lvl = q.level; // keep updating the Map so that it will have the last entry from // each level(vertically) and that will the bottom view of the tree ht.put(lvl, tnode.data); // add the left and right children of visiting nodes to the queue if (tnode.left != null) { queue.add(new QueuePack(lvl – 1, tnode.left)); } if (tnode.right != null) { queue.add(new QueuePack(lvl + 1, tnode.right)); } } } public static void display() { // print the bottom view. Set keys = ht.keySet(); for (Integer key : keys) { System.out.print(ht.get(key) + " "); } } public static void main(String[] args) { 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.right.right = new Node(8); // root.right.right.left = new Node(30); bottomView(root, 0); display(); } } class Node { int data; Node left; Node right; public Node(int data) { this.data = data; left = null; right = null; } } // this class' represents the items stored in queue (used for level order // traversal). Objects will store the nodes and its level class QueuePack { int level; Node tnode; public QueuePack(int level, Node tnode) { this.level = level; this.tnode = tnode; } }

view raw
BottomViewOfBT.java
hosted with ❤ by GitHub

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