Couting nodes with onyl one child in BST

74 views Asked by At

I am wondering how to count nodes with only one child in BST. I tried something like this:

    public int countOneChild(Node x)
   {
       if(x == null)
       {
           return 0;
       }
       /*if(x.right == null && x.left == null)
       {
           return 0;
       }*/
       if(x.left == null && x.right != null)
       {
           return 1 + countOneChild(x.right);
       }
       else if(x.left != null && x.right == null)
       {
           return 1 + countOneChild(x.left);
       }
       else 
       {
           return 0 + countOneChild(x.right) + countOneChild(x.right);
       }
   }

but this isn't working, it returns me the same result 0 every time. How can I do that?

1

There are 1 answers

1
Ryan On BEST ANSWER

The bottom else clause has a copy/paste error I believe. It should probably be:

   else 
   {
       return 0 + countOneChild(x.right) + countOneChild(x.left);
   }