Wednesday, 7 October 2015

Print a Binary Tree in Vertical Order. Find Vertical Sum of given Binary Tree.

Print Binary Tree in Vertical Order OR
Print the Binary Tree in Vertical Order Path OR
Vertical order traversal of a Binary Tree.
Find Vertical Sum of given Binary Tree

Given a binary tree, print it vertically.

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

Note:
Vertical order traversal of Tree shown above will be 
Print data present at Line 1 ( 4 )
Print data present at Line 2 ( 2 )
Print data present at Line 3 ( 1, 5, 6 )
Print data present at Line 4 ( 3 )
Print data present at Line 5 ( 7 )

Solution

Vertical order Traversal of a tree is little bit different than Pre order, Post order, In order and Level order traversal.

We need to identify, which node will be part of Line 1, Line 2, Line 3 and so on, How to do that? If you observe, then there is a close relation between each line from root.

If somehow we find out, which nodes fall in column -2, column -1, column 0, column 1 and column 2, then our task is done.

From the above image, we can see that, Root node is at scale 0.
With the reference from Root node which is at distance(column) 0, we will calculate the horizontal distance of each node at left(Negative) side and right(Positive) side.

Lets understand it with example:

  1. Node 1 is at distance 0 as this is the start point in scale. 
  2. Node 2 is at distance -1. (horizontal distance between root node 1 and node 2), as we are moving 1 column on left side of scale.
  3. Node 4 is at distance -2 (horizontal distance between root node 1 and node 4), as we are moving 2 column on left side of scale.
  4. Node 5 is at distance 0 (horizontal distance between root node 1 and node 5), as we are again on 0th column on scale. Remember we are only interested on nodes falling on same column.
  5. Node 3 is at distance +1 (horizontal distance between root node 1 and node 3), as we are moving 1 column on right side of scale.


  6. Node 6 is at distance 0 (horizontal distance between root node 1 and node 6), as we are again on 0th column on scale. 
  7. Node 7 is at distance +2 (horizontal distance between root node 1 and node 7), as we are moving 2 column on right side of scale.

From the above understanding, can we say,
If two nodes have the same Horizontal Distance from root, then they are on same vertical line.

This is what exactly we will do,
we will keep one variable horizontal distance(hd) which will keep track of horizontal distance of each node from root node,

Algorithm

1. Read the tree in Pre-order traversal

2. First node encounter will be root node, which is at hd 0 as this is starting point in scale. (hd is 0)

3. From this point, When we will move on Left, that is we are moving one column on left side, we will do (hd-1), When we will move on Right, that is we are moving one column on right side, we will do (hd+1).

4. We will take one map, which will keep dumping all the nodes found at same horizontal distance from root. (for map, key is hd and value will be nodes found).
 
For each node encountered, check whether distance is already present in map, If it is present then we already encountered nodes at same distance prior to this node, So append current node data to existing nodes.

         If it is not present then this is the first time we are encountering this distance,
         so simply store the 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.

6. Print map.


Java Program for printing Binary tree in vertical order

PrintBinaryTreeInVerticalOrder.java 
package javabypatel.tree;

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

public class PrintBinaryTreeInVerticalOrder {
 private Node rootNode;

 public static void main(String[] args) {
  new PrintBinaryTreeInVerticalOrder();
 }

 public PrintBinaryTreeInVerticalOrder(){
  addNode(rootNode, 1); 
  addNode(rootNode, 2); 
  addNode(rootNode, 3); 
  addNode(rootNode, 4); 
  addNode(rootNode, 5); 
  addNode(rootNode, 6); 
  addNode(rootNode, 7); 

  TreeMap<Integer, String> map = new TreeMap<Integer, String>();
  printTreeInVerticalOrder(rootNode, map, 0);
  
  for (Map.Entry<Integer, String> entry : map.entrySet()) {
   System.out.println(entry.getValue());
  }
 }

 private void printTreeInVerticalOrder(Node rootNode, TreeMap<Integer, String> map, int hd) {
  if(rootNode==null){
   return;
  }
  
  if(map.get(hd)!=null){
   map.put(hd, map.get(hd)+","+rootNode.getData());
  }else{
   map.put(hd, String.valueOf(rootNode.getData()));
  }
  
  printTreeInVerticalOrder(rootNode.getLeft(), map, hd-1);
  printTreeInVerticalOrder(rootNode.getRight(), map, hd+1);
 }

 
 private void addNode(Node rootNode, int data){

  //First check is there any Nodes present.
  if(rootNode==null){
   // No Nodes are Present, create one and assign it to startNode
   Node temp1=new Node(data);
   this.rootNode=temp1;
  }else{
   //Nodes present, So check the proper position where to add New Node.

   //Checking whether Left child and Right child are present for root Node. 
   if(rootNode.getLeft()!=null && rootNode.getRight()!=null){
    //Left and Right Child exist, Also, we need to add ne Node in Sequential Fashion of Left and Right, 
    //We have to scan all Levels one by one to check a proper place for new Node.
    //Also, we for each and every node we need to check whether Left and Right Exist, 
    //So we need to store them for later Processing that is why we introduced Queue.

    Queue<Node> queue = new LinkedList<Node>();
    queue.add(rootNode);

    while(!queue.isEmpty()){
     Node obj = (Node)queue.poll();
     if(obj.getLeft()!=null && obj.getRight()!=null){
      queue.add(obj.getLeft());
      queue.add(obj.getRight());
     }else if(obj.getLeft()==null){
      Node temp1=new Node(data);
      obj.setLeft(temp1);
      break;
     }else{
      Node temp1=new Node(data);
      obj.setRight(temp1);
      break;
     }
    }

   }else{
    // We reach this condition when either Left or Right is Null, but not sure which side is Null.
    if(rootNode.getLeft()==null){
     Node temp1=new Node(data);
     rootNode.setLeft(temp1);
    }else{
     Node temp1=new Node(data);
     rootNode.setRight(temp1);
    }
   }
  }
 }
}
Node.java 
package javabypatel.tree;

public class Node {
 private int data;
 private Node left;
 private Node right;

 public Node(int data) {
  this.data=data;
 }

 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 public Node getLeft() {
  return left;
 }
 public void setLeft(Node left) {
  this.left = left;
 }
 public Node getRight() {
  return right;
 }
 public void setRight(Node right) {
  this.right = right;
 }
}

In above solution, Vertical order traversal of a tree is working fine, but nodes at same level are not printed in sequence they are present because we are doing Pre-order traversal of a tree (Depth first traversal) in which Left sub-tree nodes are read first and then it picks right sub-tree.


For maintaining sequence, we have to do Breadth first traversal that is Level order traversal, which make sure nodes are Lower levels are read first than Nodes at higher level that is all Nodes at Level 0 are read first and then Node at Level 1 and then Node at Level 2 and so on.

For this we have to take a queue, which will preserve nodes at same level for later processing.

So changes that need to be done in above solution is shown below,
private static void printTreeInVerticalOrderMaintainSequence(VerticalOrderNode rootNode, TreeMap<Integer, String> map) {
 if(rootNode==null){
  return;
 }

 Queue<VerticalOrderNode> q = new LinkedList<VerticalOrderNode>();
 q.add(rootNode);

 while(!q.isEmpty()){
  VerticalOrderNode temp = q.poll();

  if(map.get(temp.getLevel())!=null){
   map.put(temp.getLevel(), map.get(temp.getLevel())+","+temp.getData());
  }else{
   map.put(temp.getLevel(), String.valueOf(temp.getData()));
  }

  if(temp.getLeftNode()!=null){
   temp.getLeftNode().setLevel(temp.getLevel()-1);
   q.add(temp.getLeftNode());
  }

  if(temp.getRightNode()!=null){
   temp.getRightNode().setLevel(temp.getLevel()+1);
   q.add(temp.getRightNode());
  } 
 }
}

class VerticalOrderNode{

 private int data;
 private VerticalOrderNode leftNode;
 private VerticalOrderNode rightNode;
 private int level;

}

Find Vertical Sum of given Binary Tree

Given a Binary Tree, find vertical sum of the nodes that are in same vertical line.
Print all sums through different vertical lines.
Let us first understand what we want to achieve? what is the input and what will be the expected output?

Solution

Solution for finding Vertical sum of binary tree is very similar to Print Binary tree vertically as we saw above.


Solution for finding Vertical sum only differ in adding the nodes at same vertical line instead of printing them all, which we did in printing Binary tree vertically above.

Lets see what we did for printing the nodes vertically, 
  
  if(map.get(hd)!=null){
     map.put(hd, map.get(hd)+","+rootNode.getData());  

     // Above line concat the data present at same vertical line.

  }else{
     map.put(hd, String.valueOf(rootNode.getData()));
  }

If we change the logic which concat the data present at same vertical line to add data at same vertical line, then our task is done. 

  
  if(map.get(hd)!=null){
     map.put(hd, String.valueOf( Integer.parseInt(map.get(hd)) + rootNode.getData()) );

     // This line sums the data present at same vertical line.

  }else{
     map.put(hd, String.valueOf(rootNode.getData()));
  }

For finding Vertical sum of binary tree, just change the above line in solution to Print Binary tree vertically and we are done.

You may also like to see

Top Binary tree interview questions in Java

Traverse a Binary Tree in Inorder, Preorder, Postorder, Levelorder traversal

Serialize and Deserialize a Binary Tree

Print Nodes visible from Top View of Binary Tree

Connvert sorted array to balanced BST

Traverse a Binary Tree in Zig Zag(Spiral) 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.

Enjoy !!!! 

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

2 comments:

  1. Bhavuk13 October 2015 at 14:45

    This code works only for first layer of the root. For the remaining nodes, the node which is nearer to the root gets printed after the node away from the root.

    For eg - Consider a tree where the values are inserted as - {1, (2,3), (4,5,6,7)}.
    Now, add 8 as right child of 5.

    Required result, 3 should be printed before 8.
    As per the algorithm, 8 gets printed before 3.

    Please correct me if I'm wrong.

    ReplyDelete
    Replies
    1. JavaByPatel13 October 2015 at 22:23

      Hi Bhavuk,

      You are absolutely right. Thanks for pointing it. Really appreciable.

      For maintaining sequence, we have to read the tree in Level Order which will make sure that Nodes at Lower levels are read first than higher levels, that is all Nodes at Level 0 are read first and then Node at Level 1 and then Node at Level 2 and so on.

      Updated the solution, I hope this is what you are looking for. Please let me know if there is any question.

      Thanks for your time.

      Delete