Page 124 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 6: Binary Search Tree and AVL Trees

6.2 Counting the Number of Nodes in a Binary Search Tree Notes

Counting 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.

Lab Exercise Program: A complete C program to count the number of nodes is as follows:
#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;

LOVELY PROFESSIONAL UNIVERSITY 119