Counting if a node has any children in BST

user_16091165 0
Viewed 83

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.

image

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.

binary-search-tree children recursion c
2 Answers

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;
}
user_40623540

The answer by MikeCAT is perfectly valid but I would like to give another viewpoint: count all the nodes in a tree and then just subtract 1 from it to account for the root.

static int countNodes (treeNode* root) {
    if (root == NULL) return 0;
    return (1 + countNodes (root->left) + countNodes (root->right));
}

static int countChildren (treeNode * root) {
    if (root == NULL) return 0;
    return countNodes (root) - 1;
}
user_151393560
Related