binary tree numNodes

Question

int numNodes() const {
   int size = 1;

   if (left != NULL) size += left->numNodes();
   if (right != NULL) size += right->numNodes();

   return size;
}

the code above is the code to find number of nodes inside a tree, as it is using recursive call, I don't really understand what it does. could anyone please explain how recursive call or function above works. Thanks

---

See also:

• Understanding recursion

Answer 1

One of the keys to understanding recursion is noticing that you're solving the same problem over and over.

The original problem is "how many nodes are in this tree?" You can solve this problem by adding the nodes in the left sub-tree and the right sub-tree. Now you have two smaller problems: counting the nodes are in the left and right sub-trees.

And here's the trick: these two smaller problems (counting the nodes in the sub-trees) are almost identical to the problem that you started with (counting all the nodes). The only difference is that the sub-trees are a little smaller than the original tree.

A clever recursive algorithm, like the one you posted, will take advantage of the similarity between these problems to solve the problem with very little code.

Recursive code is really hard to get your mind around at first. Make up an example tree and work through it, pretending to be the computer, until you believe it.

Answer 2

A recursive function is a function that calls itself.

Let's take the example you provided:

1. Begin with the top node, so size is 1. Each node has a right and left tree.
2. If a left tree exists, add the number of nodes in the left tree.
3. If a right node exists, add the number of nodes in the right tree.
4. Return size.

Steps 2 and 3 utilize recursion, because they call the function again, but using the child nodes. I'm not sure if this is technically recursion, because the function called belongs to a different object. In any case, let's take an example data set.

Let's look at a this tree:

a
|\
b c
| |\
d e f

1. We begin by calling a.numNodes(), size is 1 at this point.
2. a.left is b, so we call b.numNodes().
3. b.left is d, so we call d.numNodes().
4. d.left and d.right are null, so we return 1.
5. b.right is null, so the total weight of it's leaves are 1, and we add that to the the original size of1, so b.numNodes returns 2.
6. We go back to a, a.right is c, so we call c.numNodes().
7. c.left is e, e.numNodes() returns 1, we add that to f.numNodes() to get 2, then we add 1 for c, and return 3.
8. now a.left.numNodes() = 2 and a.right.numNodes() = 3, add those for 5 and add 1 for a, getting a final result of 6 nodes in the tree.

Hope this helps!

Answer 3

Basically this function will take the current node (which already has size 1), then add the number of nodes to the left and right of this node. Line by line:

int numNodes() const {

Declares the function numNodes(). This function is valid for any node in the tree, and every node may have a left child, a right child, or both.

int size = 1;

Since we're operating on a node, we know the size is going to start at 1 (this node).

if (left != NULL) size += left->numNodes();
if (right != NULL) size += right->numNodes();

Gets the number of nodes from both the left and right children, if they exist. This is the recursive call - it runs this same method on both child nodes and returns the result. If there are no children, numNodes() will return 1.

return size;

Gives back the size of the tree rooted at this node. Eventually, after all the recursive calls, calling numNodes() on the root of the entire tree will return the total number of nodes.

Answer 4

This code starts with size = 1, and then it increments the size every time it finds a node that's not equal to NULL.

if (left != NULL) size += left->numNodes();

This statement calls the numNodes function for the left node if the left node is not NULL, and then it returns the size of the left node and increments the size by the size of the left node.

The same is done for the right node.

Answer 5

Imagine you have a root node with left and right pointers to subnodes.

The algorithm iterates over each node and for each node it calculates it's size as:

size of left subnode + size of right subnode + 1 (for this node)

Imagine tree:

     B
    / \
   A   C

1. You call numNodes on your root node B.
2. in B it sets size = 1, calls numNodes on left subnode (A)
3. in A, since it's leaf node it returns size 1
4. in B node calles numNodes on right node (C)
5. in C, since it's leaf node it returns size 1
6. in B (left->numNodes() returned 1, right->numNodes() returned 1) adds 1 and returns 3