Question

CODE IN JAVA**
V. Given a pointer to the root of a binary tree and a pointer ‘p’ to a given node in the tree and a second pointer ‘q’ to another node in the tree write a routine which will return the total number of nodes in the tree that are on level ‘p’ and ‘q’. If they are on the same level you should multiply the answer by 3.

Answer 1

// To find the level of a given node a
   public static int level(Node head,Node a,int level)
   {
       if(head==null)
           return 0;
       if(a==head)
           return level;
       int temp=level(head.left,a,level+1); // find the node in left subtree
       if(temp!=0) // if node is present in left subtree return the level else recure for right subtree
           return temp;
       return level(head.right,a,level+1);
      
   }
  
   public static int countNodeAtLevelA(Node head ,int a,int level)
   {
       if(head==null||a<0)
           return 0;
       int count=0;
       if(a==level) // if the current level matches with the required level
       {
           count+=1;
          
       }
       count+=countNodeAtLevelA(head.left,a,level+1); // recur for left subtree
       count+=countNodeAtLevelA(head.right,a,level+1); // recur for right subtree
       return count; // return the total count
   }
  
   public static int countNode(Node root,Node p,Node q)
   {
       int level1=level(root,p,0); // find the level of node p
       int level2=level(root,q,0); // find the level of node q
       int count1=countNodeAtLevelA(root,level1,0); // count the node at level a
       if(level1==level2)
           return count1*3;
       count1+=countNodeAtLevelA(root,level2,0); // count the node at level b
       return count1;
   }