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.

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

Towers of Hanoi

The 'Towers of Hanoi' is a classical problem used to illustrate the power of recursion. 

Problem Explanation:- There are 3 pegs say A, B and C. Peg A is starting peg, Peg B is intermediate peg and Peg C is destination peg. Peg A has disc of different size. Each disc are of different size (i.e. no two disc can be of same size) and smaller disc should always be on top of big disc. We need to move disc from peg A to peg C with small disc on top and big disc at the bottom.

Lets take example with Peg A having 2 disc.

In order to move all disc from Peg A to Peg C  in same order using intermediate Peg B. First, 

move disc 1 from Peg A to Peg B

          disc 2 from Peg A to Peg C

          disc 1 from Peg B to Peg C

Now try the above step with Peg A having 3 disc.

• Move 2 disc (i.e. disc 1 and disc 2 ) from Peg A to Peg B as above example (consider Peg C as intermediate Peg)
• Move disc 3 to Peg C
• Move disc 1,2 from Peg B to Peg C  (consider Peg A as intermediate Peg)

Similarly, we have to follow 3 step for n disc are as follows:

• Move (n-1) disc from Peg A to Peg B (Peg C as intermediate Peg)
• Move n th disk from Peg A to Peg C
• Move (n-1) disc from Peg B to Peg C (Peg A as intermediate Peg)

Now we will translate the above steps to programming steps:

 public void solve(int n, String startPeg, String intermediatePeg, String endPeg){
  if(n==1){
   System.out.println(startPeg +"--->>>"+endPeg);
  }else{
   /*
    * step 1: end Peg will act as intermediate Peg and intermediate 
    * Peg will become end Peg.
    */
   solve(n-1,startPeg,endPeg, intermediatePeg);
   
   /*
    * Step 2: move n th disk from start peg to end peg
    */
   System.out.println(startPeg +"--->>>"+endPeg);
   
   /*
    * Step 3: intermediate peg will act as start peg and start peg will act as 
    * intermediate peg
    */
   solve(n-1, intermediatePeg, startPeg, endPeg);
  }
 }

Time Complexity:

from the above steps
          T(n) = T(n-1) + C + T(n-1)
          i.e.  time complexity for n disc = [time complexity for n-1 disc in step1] + [constant time need to move disc from start peg to end peg] +  [time complexity for n-1 disc in step3]

           T(n-1) = 2T(n-1)+ C (C is constant so consider it as 1)
           T(n-1) = 2T(n-1)+ 1
                      = 2( 2T(n-2) + 1 ) + 1
                      = 4T(n-2)+2+1
                      =4(2T(n-3) +1) + 2 + 1
                      =8T(n-3) +4 + 2 +1
                      = (2^n)T(n-n) + (2^(n-1)) + ......+ 4 + 2 + 1 (let T(0) = 0)
                      = (2^(n-1)) + ......+ 4 + 2 + 1
                      = (2^n)-1 = O(2^n)

Optimized way to find count of Prime Number existence between 1 to N

  A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.  A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime because 1 and 5 are its only positive integer factors.  whereas 6 is composite because it has the divisors 2 and 3 in addition to 1 and 6.

Single-threaded implementation to find Prime Number Between 1 to N where N can be any positive Number.

 static int getNumberOfPrimes(int n) {  
          List<Integer> primeNumberList = new ArrayList<>();       
          int counter = 0;  
          boolean isNotPrime = false;  
          Long startTime = System.nanoTime();  
          if(n>2){  
               primeNumberList.add(2);  
               counter++;  
          }  
          for(int i=3; i<=n; i=i+2){  
               isNotPrime = false;  
               for(int k:primeNumberList){  
                    if(k<=Math.sqrt(i) && i%k==0){  
                isNotPrime = true;  
                break;  
                    }  
               }  
            if(!isNotPrime){  
                 primeNumberList.add(i);  
              counter++;  
            }  
          }  
          System.out.println("Total Execution Time::"+(System.nanoTime()-startTime)+" nanosec");  
          return counter;  
        }  

Above program was executed to find prime number between 1 to 1000000 in corei5 processor.
It took near about 47 sec to find prime number between 1 to 1000000.

In Order to optimize the above program, I used multi-threading and the result is just amazing. It gives the count of prime number between 1 to N (i.e. 1000000) within a second.

Mutli-thread implementation to find Prime Number Between 1 to N where N can be any positive Number.

 import java.util.concurrent.Callable; 
 
 public class PrimeNumber implements Callable<Integer> {  
      private int startRange;  
      private int endRange;  
      public PrimeNumber() {  
           // TODO Auto-generated constructor stub  
      }  
      public PrimeNumber(int startRange, int endRange) {  
           this.startRange = startRange;  
           this.endRange = endRange;  
      }  
      @Override  
      public Integer call() throws Exception {  
     int counter = 0;  
     boolean isNotPrime = false;  
     if(startRange%2==0)  
          startRange++;  
     if(startRange < 2 && endRange > 2){  
          startRange = 3;       
          counter++;  
     }  
     for(int i=startRange; i<endRange; i+=2){  
          isNotPrime = false;  
          for(int j=3; j<=Math.sqrt(i); j+=2){  
               if(i%j == 0){  
                    isNotPrime = true;  
                       break;  
               }  
          }  
          if(!isNotPrime){  
         counter++;  
       }  
     }  
     return counter;  
      }  
 }  

Test Class for execution of above mutli-thread program

 import java.util.ArrayList;  
 import java.util.List;  
 import java.util.concurrent.Callable;  
 import java.util.concurrent.ExecutionException;  
 import java.util.concurrent.ExecutorService;  
 import java.util.concurrent.Executors;  
 import java.util.concurrent.Future;

  
 public class PrimeNumberTest {  
      public static void main(String[] args) throws InterruptedException, ExecutionException {  
           List<Callable<Integer>> todo = new ArrayList<Callable<Integer>>();       
           ExecutorService executor = Executors.newFixedThreadPool(6);  
           int upperRange = 1000000;  
           Long startTime = System.nanoTime();  
           for(int i=1; i<=upperRange; i+=100000){  
                if(upperRange < 100000){  
                     todo.add(new PrimeNumber(i,upperRange));  
                }else{  
                     todo.add(new PrimeNumber(i,i+100000));  
                }  
           }  
           int sum = 0;  
           List<Future<Integer>> answers = executor.invokeAll(todo);  
           executor.shutdown();  
           for(Future<Integer> taskResult: answers){  
                sum+=taskResult.get();  
           }  
           System.out.println("Total PrimeNumber between 1 to "+upperRange+" is "+sum);  
           System.out.println("Total Execution Time::"+(System.nanoTime()-startTime));  
      }  
 }