Counting if a node has any children in BST

Question

I am having a problem where I know how to count all the nodes in a tree like this return 1 + rightchild(tree->right) + rightchild(tree->left); now my problem is how would I count if a node has any children in that node, image to showcase what I am trying to do.

static int rightchild(const treeNode* tree){

    if(tree == NULL){
        return 0;
    }

    if(tree->right !=NULL){
        return 1 + rightchild(tree->right) + rightchild(tree->left);
    }
    else {
        return rightchild(tree->left);
    }

}

static int leftchild(const treeNode* tree){

    if(tree == NULL){
        return 0;
    }

    if(tree->left != NULL){
        return 1 + leftchild(tree->right) + leftchild(tree->left);
    }
    else {
        return leftchild(tree->right);
    }

}

Hopefully I am on the right path and I am just missing something I combine the result of both functions, but it is always inaccurate by one.

Answer 1

You should count the number of children in the current node and add the sum of number of children of the child nodes to that.

static int countchild(const treeNode* tree) {
    int childrenNum = 0;
    if (tree == NULL) {
        return 0;
    }
    if (tree->left != NULL) {
        /* this node has a child in left + add the number of children in the left subtree */
        childrenNum += 1 + countchild(tree->left);
    }
    if (tree->right != NULL) {
        /* this node has a child in right + add the number of children in the right subtree */
        childrenNum += 1 + countchild(tree->right);
    }
    return childrenNum;
}