Program for count the total number of node in binary tree?

Answer 1

The number of nodes in any subtree is the number of nodes in its left subtree, plus the number of nodes in its right subtree, plus one, so you can use a recursive algorithm and start at the root.

unsigned intbinarytree_count_recursive(const node *root)

{

unsigned int count = 0;

if (root != NULL) {

count = 1 + binarytree_count_recursive(root->left)

+ binarytree_count_recursive(root->right);

}

return count;

}

Answer 2

int count (const Tree *t)

{

int sum;

if (!t) return 0;

else sum=1;

if (t->left) sum += count (t->left);

if (t->right) sum += count (t->right);

return sum;

}

advanced:

int count (const Tree *t)

{

int sum= 0;

while (t) {

sum++;

if (t->left) {

if (t->right) sum += count (t->right);

t = t->left;

} else t = t->right;

}

return sum;

}

Answer 3

#include <stdio.h>

#include <stdlib.h>

/* A binary tree node has data, pointer to left child

and a pointer to right child */

struct node

{

int data;

struct node* left;

struct node* right;

};

/* Function to get the count of leaf nodes in a binary tree*/

unsigned int getLeafCount(struct node* node)

{

if(node NULL && node->right==NULL)

return 1;

else

return getLeafCount(node->left)+

getLeafCount(node->right);

}

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */

struct node* newNode(int data)

{

struct node* node = (struct node*)

malloc(sizeof(struct node));

node->data = data;

node->left = NULL;

node->right = NULL;

return(node);

}

/*Driver program to test above functions*/

int main()

{

/*create a tree*/

struct node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->left->right = newNode(5);

/*get leaf count of the above created tree*/

printf("Leaf count of the tree is %d", getLeafCount(root));

getchar();

return 0;

}