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 Treeas 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:

import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.TreeMap;
public class BottomViewOfBT {
public static TreeMap<Integer, Integer> ht = new TreeMap<>();;
public static void bottomView(Node root, int level) {
if (root == null)
return;
// create a queue for level order traversal
Queue<QueuePack> 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<Integer> 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 

6 thoughts on “Print the Bottom View of the Binary Tree.”

  1. how would the tpre-order traverse guarantee most recent visited node would be at “bottom” of a vertical level?
    Would following 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 vertical level of node(8) but lower.
    root.right.right = new Node(8);
    We should get 4 6 5 7 9 as bottom view, but my guess is the code will return 4 6 5 7 8 (wrong result)

    Reply
    • Hi Xiaozhen,

      Code is correct and will return 4 6 5 7 9, don’t concentrate on preorder traversal, we are storing the node at each vertical level in a hash map ( in fact we are updating it so hash map will contain the last node visited at that level) See the diagram.

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

    private static 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);
    }

    Reply
  3. The diagram shows doing Level +1, while going left, but in code, its doing Level-1, while traversing left. Can you please explain

    Reply

Leave a Reply to kumar Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.