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 a code for finding the number of nodes within a tree, since it uses a recursive call, I really don't understand what it does. can anyone explain how the recursive call or function above works. Thanks

---

See also:

• Understanding recursion

Answer 1

One of the keys to understanding recursion is that you are solving the same problem over and over again.

Original problem: "How many nodes are in this tree?" You can solve this problem by adding nodes to the left subtree and the right subtree. Now you have two smaller problems: counting nodes in the left and right subtrees.

: ( ) , ( ). , .

, , , .

. , , .

Answer 2

- , .

:

• node, 1. node .
• , .
• node, .
• .

2 3 , , . , , . , .

:

a
|\
b c
| |\
d e f

• a.numNodes(), 1.
• a.left - b, b.numNodes().
• b.left - d, d.numNodes().
• d.left d.right null, 1.
• b.right null, 1, 1, b.numNodes 2.
• a, a.right - c, c.numNodes().
• c.left is e, e.numNodes() 1, f.numNodes(), 2, 1 c 3.
• a.left.numNodes() = 2 a.right.numNodes() = 3, 5 1 a, 6 .

, !

Answer 3

node ( 1), node. :

int numNodes() const {

numNodes(). node , node , , .

int size = 1;

node, , 1 ( node).

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

, , . - . , numNodes() 1.

return size;

, node. , numNodes() .

Answer 4

, node .

node node :

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

:

     B
    / \
   A   C

• numNodes node .
• B size = 1, numNodes (A)
• A, node it 1
• B node numNodes node (C)
• C, node it 1
• B (left- > numNodes() 1, right- > numNodes() 1) 1 3

Answer 5

This code starts with size = 1, and then it increases the size every time it finds a node that is not NULL.

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

This statement calls the function numNodesfor the left node if the left node is not NULL, and then returns the size of the left node and increases the size by the size of the left node.

The same thing is done for the correct node.