Write a recursive function which, given the root pointer of a binary tree returns the number of leaves of the tree.

Source Code

Brief explanation is provided after the source code.

#include <stdio.h>
#include <stdlib.h>

struct tnode{
    int number;
    struct tnode *left; /* left Child */
    struct tnode *right; /* right Child */
};

int getLeafCount(struct tnode*); /* Compute number of leaves */
struct tnode *addtree(struct tnode*, int);
void treeprint(struct tnode*);
struct tnode *root;
struct tnode *talloc(void);
int *dupnum(int *);

int main(int argc, char **argv){
    FILE *in;
    const char * fn = "integer_file";
    char buff[0x200];
    root = NULL;  /* empty tree */

    if((in = fopen(fn,"rb")) == NULL){
        printf("Cannot open input file.\n");
        exit(1);
    }

     // Read integers from a file and add to a tree node
    while (fgets(buff, sizeof buff, in)) {
        root = addtree(root, atoi(buff));
    }

    printf("Tree is traversed in-order\n");
    treeprint(root);
    printf("\nNumber of Leaves: %d\n", getLeafCount(root));
    fclose(in);
    return 0;
}

/* Compute number of leaves of tree */
int getLeafCount(struct tnode* p) {

    if(p == NULL)
        return 0;
    if(p -> left == NULL && p -> right == NULL)
        return 1;
    else
        return getLeafCount(p -> left) + getLeafCount(p -> right);

}

/* addtree: add a node with n, at or below p */
struct tnode *addtree(struct tnode *p, int n){
    int cond;
    if (p == NULL){
        p = talloc();
        p -> number = dupnum(n);
        p -> left = p -> right = NULL;
    }else if (n <= p->number)
        p -> left = addtree(p -> left , n);
    else
        p -> right = addtree(p -> right , n);

    return p;
}


/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p){

    if (p != NULL) {
        treeprint(p -> left);    /* Begin with left sub tree */
        fprintf(stdout,"%d\n" ,p -> number);     /* Output number */
        treeprint(p -> right);   /* then move to right sub tree */
    }
}

/* talloc: make a tnode */
struct tnode *talloc(void) {
    return (struct tnode *) malloc(sizeof(struct tnode)); 
}

/* duplicate a number */
int *dupnum(int *n){
    char *p;
    /* make a duplicate of n */
    p = (int *) malloc(sizeof(int));
    if(p != NULL)
        p = n;
    return p;
    free(p);
}

When you compile and execute the above program it produces the following result on Linux:

Tree is traversed in-order
-7
-6
-1
10
10
12
23
100

Number of Leaves: 3

Brief Explanation

  • Nodes with no children are called leaf (or external, or terminal) nodes.
  • The function getLeafCount is a recursive function which returns the number of leaves of the tree.
  • The function takes the root pointer of the tree as parameter and returns 0 if it's NULL.
  • If the root has no children, then the function returns 1 otherwise it calls itself taking a pointer to the left and a pointer to the right subtree as parameter.

Add comment


Security code
Refresh