JavaByPatel: Data structures and algorithms interview questions in Java: 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).

3. 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.

4. 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).

5. Print map.

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

TopViewOfBinaryTree.java

package javabypatel.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);
   }
  }
 }

}

NodeForTopView.java

package javabypatel.tree;

public 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;
 }
 
}

JavaByPatel: Data structures and algorithms interview questions in Java

Thursday, 8 October 2015

Print Nodes in Top View of Binary Tree

Print the top view of Binary Tree

Solution

Algorithm

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

You may also like to see

Top Binary tree interview questions in Java

Print a Binary Tree in Vertical Order

Print Nodes in Bottom View of Binary Tree

Traverse a Binary Tree in Level Order Traversal

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

Print nodes at K distance from Leaf node in Binary tree.

Construct a Binary Tree from In-order and Post-order traversals.

When to use SOAP over REST Web Service. Is REST better than SOAP?

Tower Of Hanoi Program in Java.

No comments:

Post a Comment