Counting nodes of Binary Search Tree

To count the number of nodes in a given binary tree, the tree is required to be traversed recursively until a leaf node is encountered. When a leaf node is encountered, a count of 1 is returned to its previous activation (which is an activation for its parent), which takes the count returned from both the children’s activation, adds 1 to it, and returns this value to the activation of its parent. This way, when the activation for the root of the tree returns, it returns the count of the total number of the nodes in the tree.

#include <stdio.h>
#include <stdlib.h>
struct tnode {
	int data;
	struct tnode *lchild, *rchild;
};
int count(struct tnode *p) {
	if (p == NULL)
		return (0);
	else if (p->lchild == NULL && p->rchild == NULL)
		return (1);
	else
		return (1 + (count(p->lchild) + count(p->rchild)));

}

struct tnode *insert(struct tnode *p, int val) {
	struct tnode *temp1, *temp2;
	if (p == NULL) {
		p = (struct tnode *) malloc(sizeof(struct tnode)); 
                  /* insert the new node as root node*/
		if (p == NULL) {
			printf("Cannot allocate\n");
			exit(0);
		}
		p->data = val;
		p->lchild = p->rchild = NULL;
	} else {
		temp1 = p;
		/* traverse the tree to get a pointer to that node whose child will be the newly 
               created node*/
		while (temp1 != NULL) {
			temp2 = temp1;
			if (temp1->data > val)
				temp1 = temp1->lchild;
			else
				temp1 = temp1->rchild;
		}
		if (temp2->data > val) {
			temp2->lchild = (struct tnode*) malloc(sizeof(struct tnode));
			/* inserts the newly created node
			as left child*/
			temp2 = temp2->lchild;
			if (temp2 == NULL) {
				printf("Cannot allocate\n");
				exit(0);
			}
			temp2->data = val;
			temp2->lchild = temp2->rchild = NULL;
		} else {
			temp2->rchild = (struct tnode*) malloc(sizeof(struct tnode));
			/*inserts the newly created node
			as left child*/
			temp2 = temp2->rchild;
			if (temp2 == NULL) {
				printf("Cannot allocate\n");
				exit(0);
			}
			temp2->data = val;
			temp2->lchild = temp2->rchild = NULL;
		}
	}
	return (p);
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p) {
	if (p != NULL) {
		inorder(p->lchild);
		printf("%d\t", p->data);
		inorder(p->rchild);
	}
}
int main() {
	struct tnode *root = NULL;
	int n, x;
	printf("Enter the number of nodes\n");
	scanf("%d", &n);
	while (n -- > 0)
	{
		printf("Enter the data value\n");
		scanf("%d", &x);
		root = insert(root, x);
	}
	inorder(root);
	printf("\nThe number of nodes in tree are :%d\n", count(root));
	getchar();
	return 0;
}

Explanation

Input: 1. The number of nodes that the tree to be created should have
2. The data values of each node in the tree to be created
 
Output: 1. The data value of the nodes of the tree in inorder
2. The count of number of node in a tree.
 

Example

Input: 1. The number of nodes the created tree should have = 5
2. The data values of the nodes in the tree to be created are: 10, 20, 5, 9, 8
 
Output: 1. 5 8 9 10 20
2. The number of nodes in the tree is 5