Understanding recursive functions

Based on the binary tree below, what would the output be of the function call mystery(root)?

 struct treenode {
      int data;
      struct treenode* left;
      struct treenode* right;
 }

 void mystery(struct treenode* root) {
     if (root == NULL) return;

     mystery(root->right);
     mystery(root->left);

     if (root->data%2 == 0) {
         root->data /= 2;
     }
     else {
         int sum = 0;
         if (root->left != NULL) sum += root->left->data;
         if (root->right != NULL) sum += root->right->data;
         root->data += sum;
     }
     printf(“%d “, root->data);
}

Binary Tree: 63 | 47 16 | 86 32 NULL 9 | NULL NULL 95 NULL NULL NULL 53 64 |

This is my understanding of the function:

mystery(63->right)
mystery(63->left)

Then it's going to check to see if root->data (63) is odd or else Since it's odd, then

sum += root->left(47)
sum += root->right(16)
root->data(63) += sum, 

so now sum = ?

And then开发者_高级运维 it's going to recursively call mystery(46) and mystery(16)

Is this the right idea?

Note that the recursive calls to the children of a given node occur before the calculation of the value that node. (This may be clear to you, but I can't tell from the way you have stated your question.) Thus, by the time the sum at the root node (value 63) is computed, the values of its two children have been modified. (See below)

If a node has an odd value, its new value will be the sum of it's own value and the new values of its children, assigned by the recursive calls. Strangely, if the value of a given node is even to begin with, its new value has nothing to do with the values of its children. It will simply be half of its original value.

Since your question seems to be about understanding the flow of the recursion in general, maybe these diagrams will help. Here is the original tree:

             [63]
            /   \
         [47]   [16]
         /  \       \
      [86]  [32]    [9]
         \         /  \
        [95]    [53]  [64]

Here are the new values after calling the mystery function:

              106+8+63=[177]
                  /         \
    43+16+47=[106]          16/2=[8]
           /      \                 \
    86/2=[43]   32/2=[16]        53+32+9=[94]
           \                            /    \
      95+0=[95]                53+0=[53]  64/2=[32]

To understand the order in which things happen, keep in mind that the value of each node is computed and printed after the recursive calls to its children. This is called a "post order traversal", although usually you recursively visit the children from left to right, whereas here we are visiting them from right to left. The following diagram shows the order in which nodes are visited.

                 9[177]
               /       \
           8[106]      4[8]
         /      \          \
      7[43]     5[16]      3[94]
         \                 /   \
        6[95]          2[53]   1[32]

Printing the node values results in the following output:

32 53 94 8 16 95 43 106 177

Probably overkill, but I hope that helps.

For every node of this tree, this code is doing the following.

1. If the data of node is an even value, it is dividing it by 2 and printing the resultant value.
2. If the data of node is an odd value, it is adding the data of both of its children in it and printing the resultant value.

For example, the node containing data as 86, it is printing 43. And for node containing data as 47, it is printing 47+86+32 = 165.