Question

Suppose a binary tree stores integers. Write efficient methods (and give their Big-Oh running times) that take a reference to a binary tree root T and compute

a. the number of nodes with two children that contain the same value

**JAVA**

Answer 1

/* recursive method returns numbers of nodes with two children that contain the same value */

public int numberOfNodes(BtreeNode T)
{
   //check if T is null or both children are null then return 0
   if(T==null || T.leftChild==null && T.rightChild==null)
       return 0;
  
   //check if left child is null then call recursively with right child
   if(T.leftChild==null)
       return numberOfNodes(T.rightChild);
      
   //check if right child is null then call recursively with left child
   if(T.rightChild==null)
       return numberOfNodes(T.leftChild);
  
   //check if both two children contain the same value
   if(T.leftChild.data == T.rightChild.data)
       return (1 + numberOfNodes(T.leftChild) + numberOfNodes(T.rightChild));
   else
       return (numberOfNodes(T.leftChild) + numberOfNodes(T.rightChild));  
}

Since all the node in the binary tree need to check whether its two children contain the same value or not. Therefore, the running time of this method in big O notation is O(n), where n is the number of nodes in the binary tree.

Note: Whether you need any modification then share with me in the comment section, I'll happy to help you.

In this solution, I have checking whether the left and right child are null or not. When I will compare the data part of the children, and if any of children is null then JVM arises an Exception. Therefore, we should check beforehand, whether any node is null or not.

There are four possibilities: (1) both children are null, (2) left child is null, (3) right child is null, (4) both are not null
(1)When both children are null, that means it is a leaf node, so it returns 0
(2)When left child is null then we can process with the right subtree (since right child is not null)
(3)When right child is null then can process with the left subtree (since left child is not null)
(4)When both are not null then we can check their data parts, there are two possibilities
(a) data parts are equals (b) data parts are unequal
(a) When data parts are equals then returns 1 plus the counts of left-subtree and right-subtree (which is called recursively)
(b) data parts are unequal then returns the counts of left-subtree and right-subtree (which is called recursively) only

Note: Whether you need any modification then share with me in the comment section, I'll happy to help you.