Tuesday, June 30, 2015

Print Left View and Right View of Binary Tree

Given a Binary Tree, print Left and Right view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from Left side. and Right view of Binary Tree is set of nodes visible when tree is visited from Right Side.

Binary Search Tree
   
The Left view, all nodes that are first nodes in their levels. A simple solution is to do level order traversal and print the first node in every level. Similarly, for the Right view, all nodes that are last nodes in their levels. A simple solution is to do level order traversal and print the last node in every level.
But the above approach needs extra memory block to store all level nodes and print first node. To solve this problem with better memory complexity, We will take another approach. Maximum extra memory block required is equal to height of tree. We will use pre-order traversal in this approach.

We create boolean flag array of size = height of tree.
 levelNodeVisitedFlag = new Boolean[height];  
 Arrays.fill(levelNodeVisitedFlag, Boolean.FALSE);  
                              
As we traverse first node in a level, we set boolean flag for that level to 'true'. We have to keep level information of a visiting node.
From above BST, node 20 is at level-0. As soon as node 20 is traversed, set levelNodeVisitedFlag[0]= true. Then traverse node 10 and node 8 and set levelNodeVisitedFlag[1] and levelNodeVisitedFlag[2] to true. In next step, node 15 at level-2  is to be visited. Since  levelNodeVisitedFlag[2] is already set to 'true' this node data is not printed and It keeps on traverse other node and check levelNodeVisitedFlag for respective level before printing node data.

Java Tree Node 
 /*  
  * @Author: Amit Kumar  
  * @Email: amit.anjani89@gmail.com  
  */  
 public class TreeNode {  
      private int data;  
      private TreeNode leftChild;  
      private TreeNode rightChild;  
      public TreeNode() {  
           // TODO Auto-generated constructor stub  
      }  
      public TreeNode(TreeNode leftChild, int data ,TreeNode rightChild) {  
           this.leftChild = leftChild;  
           this.data =data;  
           this.rightChild = rightChild;  
      }  
      public int getData() {  
           return data;  
      }  
      public void setData(int data) {  
           this.data = data;  
      }  
      public TreeNode getLeftChild() {  
           return leftChild;  
      }  
      public void setLeftChild(TreeNode leftChild) {  
           this.leftChild = leftChild;  
      }  
      public TreeNode getRightChild() {  
           return rightChild;  
      }  
      public void setRightChild(TreeNode rightChild) {  
           this.rightChild = rightChild;  
      }  
 }  

Java Code to create Binary Search Tree
 public void createBST() {  
           //Test data  
           int[] itemArray= {20,10,25,8,15,23,28,14,18,12,11};  
           // Create BST  
           for(int item:itemArray){  
                insertIntoBST(item);  
           }  
      }  
     /*  
     * Adding node to a bst  
     */  
    private void insertIntoBST(int item) {  
        if (rootNode == null) {  
             rootNode = new TreeNode(null, item, null);  
        } else {  
             insertIntoBST(rootNode, item);  
        }  
    }  
    
    private void insertIntoBST(TreeNode node, int item) {  
        if (item < node.getData()) {  
          if (node.getLeftChild() == null) {  
            node.setLeftChild(new TreeNode(null, item, null));  
          } else {  
               insertIntoBST(node.getLeftChild(), item);  
          }  
        } else if (item > node.getData()) {  
          if (node.getRightChild() == null) {  
            node.setRightChild(new TreeNode(null, item, null));  
          } else {  
               insertIntoBST(node.getRightChild(), item);  
          }  
        }  
      }  

Java code to find height of Binary Tree
 private int heightOfBST(TreeNode node){  
       if(node == null)  
           return 0;  
       return max(heightOfBST(node.getLeftChild()),heightOfBST(node.getRightChild()))+1;  
 }  

Jave Code to print Left view of Binary Tree
      /*  
       * Left view Tree traversal  
       */  
      private void leftViewTreeTraversal(TreeNode node){  
           ++level;  
           if(node==null)  
                return;  
           if(!levelNodeVisitedFlag[level]){  
                levelNodeVisitedFlag[level] = true;  
                System.out.println(node.getData());  
           }  
           if(node.getLeftChild()!=null)  
                leftViewTreeTraversal(node.getLeftChild());  
           if(node.getRightChild()!=null)  
                leftViewTreeTraversal(node.getRightChild());  
           level--;  
           return;  
      }  

Java Code to print Right view of Binary Tree
      /*  
       * right view of binary search tree  
       */  
      private void rightViewTreeTraversal(TreeNode node){  
           ++level;  
           if(node==null)  
                return;  
           if(!levelNodeVisitedFlag[level]){  
                levelNodeVisitedFlag[level] = true;  
                System.out.println(node.getData());  
           }  
           if(node.getRightChild()!=null)  
                rightViewTreeTraversal(node.getRightChild());  
           if(node.getLeftChild()!=null)  
                rightViewTreeTraversal(node.getLeftChild());  
           level--;  
           return;  
      }  

No comments:

Post a Comment