Question

Write a boolean function that is given a binary tree and returns true if and only if the tree has an odd number of nodes. An empty tree is considered to have an even number of nodes. Notes: The function should have just one argument, a pointer to the root. No global variables may be used. No additional functions may be defined. You may not count the number of nodes.

Answer 1

BOOLEAN FUNCTION :

bool OddCheck(BinaryTreeNode<int>* root){
  
// if the binary tree is Empty ie. considered as even nodes.
if(root==NULL)
return false;
  
// if binary tree only contains one node ie.odd number f nodes
if(root->left==NULL&&root->right==NULL)
return true;
  
  
//if binary tree have only contains right subtree and left subtree is Empty.
else if(root->left==NULL&&root->right!=NULL){
bool a = OddCheck(root->right);
if(a==true)
return false;
else
return true;
  
}
  
//if binary tree have only contains left subtree and right subtree is Empty.
else if(root->left!=NULL&&root->right==NULL){
  
bool a = OddCheck(root->left);
if(a==true)
return false;
else
return true;
  
}
  
  
// If both Left Subtree and Right Subtree is not Empty.
else if(root->left!=NULL&&root->right!=NULL){
  
bool a = OddCheck(root->left);
bool b = OddCheck(root->right);
  
//if both subtrees have odd numbers of nodes. Then result will be odd.
if(a==true&&b==true)
return true;
  
//If both subtrees have even number of nodes then result will be:

// even + even + 1(for root) =ODD

else if(a==false&&b==false)
return true;
  
//for all other cases the result will be even numbers of nodes.
else
return false;
  
  
}
  
}