Print Nodes in Top View of Binary Tree


Print the top view of Binary Tree



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


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

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


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

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


Solution


Solution for printing the nodes visible from top 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 top 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 top view, we are only interested in first node of each column or line because that are the only nodes that will be visible from top, 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

    first 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 are good.


    Node 2 will be encountered first at Line -1 and we are good.


    Node 4 will be encountered at Line 0, we will ignore this as First element for Line 0 is already

    present in map, It means we already encountered first node of line 0.

    Node 5 will be encountered at Line 1 and check is done whether we found any node prior to

    this for line 1, which evaluate to false, and we will consider 5 as first element in Line 1.   
    We are in trouble here, Now when Node 3 will come later in picture, we will ignore it thinking that
    first element for line 1
is already present in map. 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 first element of each line/column will be encountered first.

   
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 first nodes of

    each line in map and ignore other nodes that are present on same vertical line.

3.
Print the map.


Algorithm


1. Read the tree in Level order traversal.
 

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

    For each node encountered, check whether hd is already present in map,
         If present, then we already encountered first node on same line before current node,
         so ignore and proceed

        
         If not present, then this is the first time we are encountering node of line and will be first node

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

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 top view of Binary tree.


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

PrintBinaryTreeInVerticalOrder.java
package tree;

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

public class TopViewOfBinaryTree {
 
 private NodeForTopView rootNode=null;
 private Map<Integer, NodeForTopView> map = new TreeMap<Integer, NodeForTopView>();
 
 public static void main(String[] args) {
  new TopViewOfBinaryTree();
 }

 public TopViewOfBinaryTree(){
  addNode(rootNode, 10); 
  addNode(rootNode, 5); 
  addNode(rootNode, 20); 
  addNode(rootNode, 6); 
  addNode(rootNode, 7); 
  addNode(rootNode, 8);
  
  printTopView(rootNode);
  
  for (Map.Entry<Integer, NodeForTopView> element : map.entrySet()) {
   System.out.print(((NodeForTopView)element.getValue()).getData() + " ");
  } 
 }
 
 private void printTopView(NodeForTopView rootNode) {
  
  if(rootNode==null)
   return;
 
  Queue<NodeForTopView> queue = new LinkedList<NodeForTopView>();
  queue.add(rootNode);
  
  while(!queue.isEmpty()){
   NodeForTopView nodeForTopView = (NodeForTopView)queue.poll();
   
   int currentLevel = nodeForTopView.getLevel();
   if(map.get(nodeForTopView.getLevel())==null){
    map.put(nodeForTopView.getLevel(), nodeForTopView);
   }
   
   if(nodeForTopView.getLeftNode()!=null){
    nodeForTopView.getLeftNode().setLevel(currentLevel-1);
    queue.add(nodeForTopView.getLeftNode());
   }
   
   if(nodeForTopView.getRightNode()!=null){
    nodeForTopView.getRightNode().setLevel(currentLevel+1);
    queue.add(nodeForTopView.getRightNode());
   }
  }
  
 }

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

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

}


You may also like to see


Print a Binary Tree in Vertical Order

Print Nodes in Bottom 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