CODEWITHSUNDEEP
crecursiontree
srbh
srbh

Reputation: 97

How does this function count the number of nodes in a tree?

A function to count the number of nodes in a tree. 

int count(node *t)
{    
    int i;  
    if (t == NULL)         
        return(0);  
    i = 1 + count(t->left) + count(t->right); // recursion occurs address of left node is passed and 
    return(i);                                // continue to pass until whole left node
}                                             // is traversed and the value of t is
                                              // NULL and 0 is returned same for right node counting
                                              // i = 1 + 0 + 0 = 1

How is the number of nodes counted ?

Upvotes: 2

Views: 8241

Answers (5)

Vite Falcon
Vite Falcon

Reputation: 6643

First, have you tried it yourself?

Basically, it adds 1 for every non-null node. It's roughly like this: 1 + number_of_nodes_to_the_left + number_of_nodes_to_the_right. This expands to: 1+(1+number_of_nodes_to_the_left_in_left+number_of_nodes_to_the_right_in_left) + (1+number_of_nodes_to_the_left_in_right + number_of_nodes_to_the_right_in_right). Keep on expanding and you'll see that it's basically 1 + 1 + 1 +.... for every non-null node in the tree.

EDIT: To illustrate this better, consider the following tree:

     Node0
       |
(left) |  (right)
Node1 _|_ Node2
            |
     (left) |  (right)
     Node3 _|_ Node4

When you do int node_count = count(Node0), since Node0 is not NULL, it goes to the return statement which is: return 1 + count(left) + count(right). You need to understand a basic thing that very operation in your recursion function happens one-after-the-other.In other words operation count(right) doesn't happen until operation count(left) is completed. Now take a look at the return statement you have there and translate it in terms of the above tree. It would be 1+count(Node1)+count(Node2). So count(Node2) doesn't get calculated before count(Node1) has finished. So for count(Node1), count function gets called (again) with Node1 as the argument. So let us, for now, forget about the semi-calculated expression 1+count(Node1)+count(Node2) (we'll come back to it later).

Now for count(Node1), Node1 is not NULL and hence proceeds to the return statement. This would (again) be 1+count(left)+count(right). But wait, Node1 doesn't have left and right nodes. So, when count(left) gets called with the argument being NULL, it returns 0 and the same happens for count(right). So the expression for count(Node1) becomes 1 + 0 + 0. There are no more count functions being called for Node1 and hence it returns to it's original caller, which was the return statement of count(Node0).

Since we have count(Node1) figured out, let's replace it in the return statement of count(Node0). This now becomes 1 + (1 + 0 + 0) + count(Node2).

Now I'm going to make this a bit faster. Since Node2 has two children, the return statement of Node2 will be 1 + count(Node3) + count(Node4). Just like it was for Node1, count(Node3) and count(Node4) will each return 1 + 0 + 0, turning the return statement of count(Node2) to be 1 + (1 + 0 + 0) + (1 + 0 + 0).

Now that count(Node2) has been fully calculated, let's return to the original caller of count(Node2), which is 1 + (1 + 0 + 0) + count(Node2). Replace what we got from count(Node2) in there and we get 1 + (1+0+0) + (1 + (1+0+0) + (1+0+0)). Add it up and we get the value of 5. This value gets returned to whichever function that called count(Node0), like the statement int node_count = count(Node0) and node_count will have the value 5.

Upvotes: 1

pmg
pmg

Reputation: 108988

To understand recursion, you must first understand recursion.

Upvotes: 10

user2100815
user2100815

Reputation:

Consider these trees:

A tree with no nodes (i.e. a NULL pointer) - returns 0

A tree with one node, the root. This will call:

 i=1+count(t->left)+count(t->right);

with left and right NULL, and so will return 1 + 0 + 0

A tree with a root and a single right leaf

 i=1+count(t->left)+count(t->right);

will return 1 for the root, 0 for the tree rooted at left (by the rules above) and 1 for the tree rooted at right (by the rules above), which is 1 + 0 + 1

And so on.

Upvotes: 0

dubnde
dubnde

Reputation: 4441

The total count includes the current/root node plus the count on the left branch plus the count on the right branch. Your sentinel is the NULL which means you've reached the leaf node of whatever branch you are currently counting. Then you unwind back up. Recursion :)

Upvotes: 1

sharptooth
sharptooth

Reputation: 170509

That's a recursive implementation of counting tree nodes. It is called for the root node and returns "one plus number of nodes in left subtree plus number of nodes in the right subtree", that is done recursively until it reaches leaf nodes.

Upvotes: 3

Related Questions