Recursive functional explanation in binary tree

Question

I was going through the tutorial of binary tree .
And I am slightly stuck in use of recursive function . say for example I need to count no of nodes in a tree

int countNodes( TreeNode *root )    
{   
       // Count the nodes in the binary tree to which  
       // root points, and return the answer.  
    if ( root == NULL )  
       return 0;  // The tree is empty.  It contains no nodes.  
    else
   {  
       int count = 1;   // Start by counting the root.  
       count += countNodes(root->left);  // Add the number of nodes   
                                        //     in the left subtree.   
       count += countNodes(root->right); // Add the number of nodes   
                                        //    in the right subtree.  
       return count;  // Return the total.  
    }  
 }   // end countNodes()

Now my doubt is-> how would it count say root->left->left of right ? or root->right->left->left?? Thanks

Answer 1

With recursive functions, you should think recursively! Here's how I would think of this function:

• I start writing the signature of the function, that is

  int countNodes( TreeNode *root ) 
  

• So first, the cases that are not recursive. For example, if the given tree is NULL, then there are no nodes, so I return 0.

• Then, I observe that the number of nodes in my tree are the number of nodes of the left sub-tree plus the number of nodes of the right sub-tree plus 1 (the root node). Therefore, I basically call the function for the left and right nodes and add the values adding 1 also.
  • Note that I assume the function already works correctly!

Why did I do this? Simple, the function is supposed to work on any binary tree right? Well, the left sub-tree of the root node, is in fact a binary tree! The right sub-tree also is a binary tree. So, I can safely assume with the same countNodes functions I can count the nodes of those trees. Once I have them, I just add left+right+1 and I get my result.

How does the recursive function really work? You could use a pen and paper to follow the algorithm, but in short it is something like this:

Let's say you call the function with this tree:

  a
 / \
b   c
   / \
  d   e

You see the root is not null, so you call the function for the left sub-tree:

b

and later the right sub-tree

   c
  / \
 d   e

Before calling the right sub-tree though, the left sub-tree needs to be evaluated.

So, you are in the call of the function with input:

b

You see that the root is not null, so you call the function for the left sub-tree:

NULL

which returns 0, and the right sub-tree:

NULL

which also returns 0. You compute the number of nodes of the tree and it is 0+0+1 = 1.

Now, you got 1 for the left sub-tree of the original tree which was

b

and the function gets called for

   c
  / \
 d   e

Here, you call the function again for the left sub-tree

d

which similar to the case of b returns 1, and then the right sub-tree

e

which also returns 1 and you evaluate the number of nodes in the tree as 1+1+1 = 3.

Now, you return the first call of the function and you evaluate the number of nodes in the tree as 1+3+1 = 5.

So as you can see, for each left and right, you call the function again, and if they had left or right children, the function gets called again and again and each time it goes deeper in the tree. Therefore, root->left->left or root->right->left->left get evaluated not directly, but after subsequent calls.

Answer 2

That's basically what the recursion's doing, it's adding 1 each time countNodes is called as it gets to a child node (int count = 1;) and terminating when it tries to go to the next child of a leaf node (since a leaf has no children). Each node recursively calls countNodes for each of it's left and right children and the count slowly increases and bubbles to the top.

Try and look at it this way, where 1 is added for each node and 0 for a non-existing node where the recursion stops:

          1
        /   \
       1     1
      / \   / \
     1   0 0   0
    / \
   0   0

The 1's each add up, with the node's parent (the calling function at each level of recursion) adding 1 + left_size + right_size and returning that result. Therefore the values returned at each stage would be:

          4
        /   \
       2     1
      / \   / \
     1   0 0   0
    / \
   0   0

I'm not sure that made it any clearer but I hope it did.