Question

C++ programming

Make a function or algorithm that can print/return #nodes with exactly two children in a BST

Answer 1

Here is the C++ function/algorithm for return number of nodes with exactly two children in a BST:

int countTwoChildNodes(struct Node* root)
{
// Base cases
if (root == NULL) return 0;

//if leaf node, return 0
if ((root->left == NULL) && (root->left ==null)) return 0;
  
//if node with only one children
   if ( (root->left == NULL) && (root->left ==null)){
   return (countTwoChildNodes(root->left) + countTwoChildNodes(root->right));
   }
  
   //if a node has both left and right child
if ((root->left) && (root->right)){
   return 1+(countTwoChildNodes(root->left) + countTwoChildNodes(root->right));
   }
}

Screenshot:

int countTwoChildNodes (struct Node* root) { // Base cases if (root NULL) return; == //if Leaf node, return if (root->left == NULL) && (root->left ==null)) return ; //if node with only one children if ( (root->left NULL) && (root->left ==null)){ return (count TwoChildNodes (root->left) + countTwoChildNodes (root->right)); == ... } //if a node has both left and right child if ((root->left) && (root->right)){ return 1+(count TwoChildNodes (root->left) + countTwoChildNodes (root->right)); ..... } }

Explanation:

If there are no nodes in tree or if the current node is leaf (a node which don't have both left and right children) will return 0 as count.

But if a node has only 1 children, either left or right, don't count the node but has to continue search for node with 2 children from left or right children.

If a node has both left and right child, return count as 1 and continue search for node with 2 children for left and right children.