write efficient methods that take only a reference to the ro

write efficient methods that take only a reference to the root of a binary tree T and compute: a) The number f nodes in T b) The number of leaves in T c) The number of full nodes in T what is the running time of your routines?

Solution

//This function will return the number of nodes in the tree given the root

int leaves = 0
int full_nodes = 0
int func(node *root)
{
   if(root==NULL) {return 0;}

   int a = func(root->left);
   int b = func(root->right);

   if(a==0 && b==0)
   {
       leaves = leaves + 1;
   }
   else if (a>0 && b>0)
   {
       full_nodes = full_nodes+1;
   }
   return a+b+1;
}

// At the end the function will return the number of nodes in the tree. The variables leaves and full_nodes will store the number of leaves and number of full nodes respectively.
//The run time complexity is O(n). Where n is the number of nodes in the tree.