Introduction

How would you count the number of nodes in a tree? Traverse all the nodes in a tree. You can do any traversal and just start counting. But there is a concept called tail recursion which is handy and very easily readable.

If you have a tree, if you know the number of nodes in the left and number of nodes in right +1, then, what you get is total number of nodes.

Concept

You have to do tail recursion with count(root->left) + count(root->right)+1.

After you get the count, how you will find the height of the tree ?

log_{2 }count_of_nodes. But in C++, you won’t get a function to calculate log base 2. :)

There is a way,

log_{10} n/log _{10 }2 = log _{2} n

So, you just need to use the above formula to get log base 2 which yields the height of the tree.

Code

Tree* tobj;

`int count(Tree* root) {`

` if(root == NULL)`

` return 0;`

` else `

` if(root->left == NULL && root->right == NULL)`

` return 1;`

` else`

` return count(root->left) + count(root->right) + 1; `

}

cout<<count(tobj);

- you are covering 2 base conditions here, root == NULL then 0. root->left & root->right is NULL, then only root node is there, which is 1.
- This expands to 1 for each node in the left & right.

## 5 comments:

One of my exam questions was to write this algorithm. I used your version. We'll see how good it is ;)

The Condition:

if(root->left == NULL && root->right == NULL)

return 1;

is NOT needed, if both Children are NULL, we will get 0 for them.

(root==NULL) condition is enough to serve as the base condition.

@Sandeep,

Yes Sandeep. you are right!! the extra condition is just to reduce the extra function calls.

Thanks a lot great tips,very useful by quizvook.com

I am trying to figure out how to call this function in main. :(

## Post a Comment