4

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

Improve this question
1

11 Answers 11

Reset to default
7

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

thats too good comment . I guess I know now what coding is doing. I will look into code again and if got stuck I will ping you guys again but atm it seems I have understood with your explaination
@to everyone then in function below void printTree(struct node* node) { if (node == NULL) return; printTree(node->left); printf("%d ", node->data); printTree(node->right); } in this function then when it encountered NUll after b it will encoutered node == NULLand hence return(exit from function) therefore below code like printf will not execute am i right?
@samprat, exactly. When you return from the function, you just return and don't execute whatever comes after.
3

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.

Improve this answer

Comments

2

Say you call countNodes(myTree);. Assuming myTree is not null, countNodes will eventually execute count += countNodes(root->left);, where root is myTree. It re-enters your countNodes function with the entire tree rooted at root->left (which is myTree->left). The logic then repeats itself; if there is no root->left, then the function returns 0. Otherwise, it will eventually call count += countNodes(root->left); again, but this time root will actually be myTree->left. That way it will count myTree->left->left. Later it does the same thing with the right nodes.

Improve this answer

3 Comments

But then according to my understanding , code will eventually hit the condition when root == NULL which according to your example say it happens myTree->left->left and then it will return 0 so when it will get chance to return count?
if i have inorder values of 12345 then root == 4 so it will go to left which is root->left == 2 , its not null so it will go to root->left->left ,w which is equal to 1 and after that there is no leaf so function countnodes( root->left->left->left) will become null and return 0?
@samprat The important thing to understand about recursion is that there are several copies of countNodes executing at once, each with its own count value. When root == NULL, it will return 0 to the calling function. Unless you're at the top of the tree, that will be another frame of countNodes executing for the parent node of the (sub)tree represented by root, where 0 will be added to the running value of count in that frame. When that frame returns, the value returned will be added to another count corresponding to the node two levels up from root, etc.
2

That's the beauty of recursive algorithms. The function is defined over the current node and its children. You only have to convince yourself that the current invocation is correct as long as the recursive calls to the left and right children are correct. Exactly the same reasoning applies to the children and their children, and so on ... it'll all just work.

Improve this answer

Comments

1

It will start by root->left->(subnode->left) etc. until that branch returns 0 e.g. if it is not an actual node (a leaf in the tree);

Then the deepest node will check for root->right and repeat the same procedure. Try to visualize this with a small tree :

enter image description here

So in this case your function will go A->D->B then the right nodes will all return 0 and you will get a last +1 from your C node.

Improve this answer

Comments

1

The algorithm implementation you write is exhaustive. It visit the entire tree.

If the tree is empty, count is zero. If not, we get the left node, let's call it L and we add 1 to our count.

Since it is proven that a subtree of a tree is itself a tree, we perform the same algorithm again on the tree that have L as root.

We now do it for the tree that have the root right node as root.

Now... this indeed works.

A subtree of a tree is a tree, also for empty or single nodes. You should look at the definition of tree.

You can prove it using Mathematical Induction and formulate your problem in terms of inductive reasoning. Recursive algorithms uses often a structure very similar to inductive reasoning.

Improve this answer

Comments

1

The trick with recursive functions is that there is a base case and an inductive step, just like mathematical induction.

The base case is how your recursive algorithm knows to stop. In this case it is if (root == NULL) -- this node doesn't represent a tree. This line is executed on every single node in your binary tree, even though it calls each one root at the time. It is false for all the nodes of the tree, but when you begin calling the recursive routine on the children of the leaf nodes -- which are all NULL -- then it will return 0 as the count of nodes.

The inductive step is how your recursive algorithm moves from one solved state to the next unsolved state by converting the unsolved problem into (one or more) already-solved problems. Your algorithm needs to count the number of nodes in a tree; you need 1 for the current node, and then you have two simpler problems -- the number of nodes in the tree on the left, and the number of nodes on the tree on the right. Get both of those, add them together, add the 1 for the current node, and return that as the count of nodes in this tree.

This concept really is fundamental to many algorithms in computer science, so it is well worth studying it until you fully understand it. See also quicksort, Fibonocci sequence.

Improve this answer

Comments

1

Think that the program goes first at the deepest branches. Then it goes backwards returning the count number to its previous member.

    A
   / \
  B   C
 / \   \
D   E   F

So first the program runs until

count += countNodes(root->left);

It pauses what it's done so far(aparently nothing special) and goes into B. Same happens there and it goes to D. At D it does the same. However here we have a special case. The program sees at the beginning at line

if ( root == NULL )

that the nonexistent left child of D is indeed NULL. Therefore you get back 0. Then we go back at where we paused last time and we continue like this. Last time we were at B so we continue past the line

count += countNodes(root->left);

and run the next line 

count += countNodes(root->right);

This goes on until you get back to A. But at point A again we had paused just after searching the left leave of A. Therefore we continue with the right leave. Once we are done going through whola that branch we get back to A.

At this point we don't have any unfinished business(pauses) left so we just return the count that we gathered through whole this process.

Improve this answer

Comments

0

Every subtree has its own root, just as the actual tree has a root. The counting is the same as for each of the subtrees. So you just keep going until you reach the leaf nodes and stop that local recursion, returning and adding up the nodes as you go.

Improve this answer

Comments

0

Draw the entire tree, then assign 1 for all leafs nodes (leaf nodes are at level N). After that you should be able to calculate the number of nodes that is generated by each node on a higher level (N-1) just by summing: 1 + 1 if the node has two children or 1 if the node has only one child. So for each node on level N-1, assign the value 1 + sum(left,right). Following this you should be able to calculate the number of nodes of the entire tree. The recursion that you posted, do just that.

Improve this answer

Comments

0

http://www.jargon.net/jargonfile/r/recursion.html

UPDATE: The point is that both the data structure and the program are recursive.

  • for the data structure this means: a subtree is also a tree.
  • for the code it means: counting the tree := counting the subtrees (and add one)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.