Print Nodes in Bottom View of Binary Tree.


Print the bottom view of Binary Tree



Given a binary tree, print the nodes that is visible, when the tree is viewed from the bottom.


Let us first understand what we want to achieve? what is the input and what will be the expected output?


Bottom view means, when we look the tree from the bottom, the nodes that are visible will be called the bottom view of the tree. So in the above image,

For Case 1,  Node 4, 2, 6, 3, 7 will be visible from bottom and Node 1 and Node 5 will not be visible from bottom as it will be hidden by Node 6.

For Case 2, Node 2, 4, 5, 6 will be visible and Node 1 and Node 3 will not be visible from bottom as it will be hidden by Node 4 and Node 5 respectively.


Solution


Solution for printing the nodes visible from bottom view of binary tree is very similar to vertical traversal of binary tree.

Before proceeding with the solution, it is very important to understand,
How to print the binary tree in vertical order.


We will use the same concept that we used for vertical order traversal of Binary Tree.

If two nodes have the same Horizontal Distance from root, then they are on same vertical line.


Only difference we see in solution of vertical traversal of binary tree and printing the nodes that are visible from bottom view is,

In vertical traversal of binary tree.
1. We do Pre-order traversal of binary tree.
2. Nodes that are part of same horizontal distance are clubbed together in hashmap value against key

    horizontal distance(hd).

For printing the nodes visible from bottom view, we are only interested in last node of each column or line because that are the only nodes that will be visible from bottom, others nodes will be hidden by them.

1.
If we do Pre-order traversal that is depth first traversal, then we will not able to track which is

    last node in a line. Lets understand with example,
   


    Look at above tree, If we do Pre-order traversal, then,

    Node 1 will be encountered first at Line 0 and we will store it in map.put(0, Node 1)

    Node 2 will be encountered at Line -1 and we
will store it in map.put(-1, Node 2)

    Node 4 will be encountered at Line 0, we will override the Node 1 already present against
    horizontal distance 0. It means this is the last element we encountered at line 0 till now.

    Now map status is map.put(0, Node 4).

    Node 5 will be encountered at Line 1 and
we will store it in map.put(1, Node 5)

    Node 6  will be encountered at Line 2 and we will store it in map.put(2, Node 6)

    Node 3 will be encountered at Line 1 and we will override the Node 5 already present in map
    thinking that this is the last node visited at line 1.
map.put(1, Node 3) 
    We are in trouble here, So depth first traversal will not help.

    We have to do Level order traversal here, which will process the tree level by level and make
    sure that last element of each line/column will be encountered last.

   
2. In vertical order traversal, nodes that are part of same horizontal distance are clubbed together in

    hashmap value against key hd.

    Here, instead of clubbing the nodes present on same line, we will simply put the nodes of

    each line in map and keep overriding nodes present on same line, which will make sure that all top
    nodes of same line will arrive in map first and last node of same line will override the top nodes of
    same line, and hence map will have last nodes of each line.


3.
Print the map.


Algorithm


1. Read the tree in Level order traversal.
 

2. We will take one map, which will store last nodes of each line.
    (for map, key will be horizontal distance(hd) and value will be last node of each line).
 

    For each node encountered, check whether hd is already present in map,
         If present, then we will override the node already present against the hd, as this is the last
         node we encounter on same line till now.

        
         If not present, then this is the first time we are encountering node of line, which might be last

         node of a Line, so simply store it data against hd.

         Point here is, every time we need to override the value(node) stored against the key(hd), 
         If we keep on overriding the value, then node entered at last in map will be last node of each 
         line.
         
5. Better to use TreeMap in this case, as it will store the result in ascending order,
    which we are interested in.
    (We can use TreeSet here, for simplicity I have used TreeMap).


6. Print map.

Java Program for printing nodes visible from bottom view of Binary tree.


class NodeForBottomView{
 
 private int data;
 private NodeForBottomView leftNode;
 private NodeForBottomView rightNode;
 private int level;
 
 public NodeForBottomView(int data) {
  this.data = data;
 }
 
 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 public NodeForBottomView getLeftNode() {
  return leftNode;
 }
 public void setLeftNode(NodeForBottomView leftNode) {
  this.leftNode = leftNode;
 }
 public NodeForBottomView getRightNode() {
  return rightNode;
 }
 public void setRightNode(NodeForBottomView rightNode) {
  this.rightNode = rightNode;
 }
 public int getLevel() {
  return level;
 }
 public void setLevel(int level) {
  this.level = level;
 } 
}


BottomViewOfBinaryTree.java
package tree;

import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.TreeMap;

public class BottomViewOfBinaryTree {
 private NodeForBottomView rootNode=null;
 
 public static void main(String[] args) {
  new BottomViewOfBinaryTree();
 }

 public BottomViewOfBinaryTree(){
  addNode(rootNode, 30); 
  addNode(rootNode, 10); 
  addNode(rootNode, 60); 
  addNode(rootNode, 59); 
  addNode(rootNode, 58); 
  addNode(rootNode, 55); 
  addNode(rootNode, 50); 
  
  printBottomView(rootNode);
  
  for (Map.Entry<Integer, NodeForBottomView> element : map.entrySet()) {
   System.out.print(((NodeForBottomView)element.getValue()).getData() + " ");
  }
 }
 
 private void printBottomView(NodeForBottomView rootNode) {
  if(rootNode==null)
   return; 

   Map<Integer, NodeForBottomView> map = new TreeMap<Integer, NodeForBottomView>();

  Queue<NodeForBottomView> queue = new LinkedList<NodeForBottomView>();
  queue.add(rootNode);
  
  while(!queue.isEmpty()){
   NodeForBottomView temp = (NodeForBottomView)queue.poll();
   
   int currentLevel = temp.getLevel();
   
   map.put(currentLevel, temp);
   
   if(temp.getLeftNode()!=null){
    temp.getLeftNode().setLevel(currentLevel-1);
    queue.add(temp.getLeftNode());
   }
   
   if(temp.getRightNode()!=null){
    temp.getRightNode().setLevel(currentLevel+1);
    queue.add(temp.getRightNode());
   }
  }
  
 }

 private void addNode(NodeForBottomView rootNode, int data){
  if(rootNode==null){
   NodeForBottomView temp = new NodeForBottomView(data);
   this.rootNode=temp;
  }else{
   addNodeInProperPlace(rootNode, data);
  }
 }

 private void addNodeInProperPlace(NodeForBottomView rootNode, int data){ 
  if(data>rootNode.getData()){
   if(rootNode.getRightNode()!=null){
    addNode(rootNode.getRightNode(), data);
   }else{
    NodeForBottomView temp1 = new NodeForBottomView(data);
    rootNode.setRightNode(temp1);
   }
  }else if(data<rootNode.getData()){
   if(rootNode.getLeftNode()!=null){
    addNode(rootNode.getLeftNode(), data);
   }else{
    NodeForBottomView temp1 = new NodeForBottomView(data);
    rootNode.setLeftNode(temp1);
   }
  }
 }

}


You may also like to see


Print a Binary Tree in Vertical Order

Print Nodes in Top View of Binary Tree

Traverse a Binary Tree in Level Order Traversal



Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment