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.
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 ?
log2 count_of_nodes. But in C++, you won’t get a function to calculate log base 2. :)
There is a way,
log10 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.
- 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.