Understanding recursive functions

Question

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?

Appears that your traversal path is incorrect. You should traverse the right sub-tree recursively before you look at the left. I'd advise you to use a stack to trace this - it avoids the confusion. And going further, you could just try putting some test data in the tree and test it out. — itsols
– itsols, Commented May 6, 2011 at 5:16

Joel Lee · Accepted Answer · 2011-05-06 15:33:41Z

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.

Thanks, that helps a lot. One thing, for the first value that gets printed wouldn't it be 64/2 = 32. And then that would make 3[9+32+53]. So the print output would be: 32, 53, 94, 8, 95, 16, 43, 106, 177

Aamir · Accepted Answer · 2011-05-06 05:09:53Z

0

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

If the data of node is an even value, it is dividing it by 2 and printing the resultant value.
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.

answered May 6, 2011 at 5:09

Aamir

15.8k6 gold badges49 silver badges72 bronze badges

Collectives™ on Stack Overflow

Understanding recursive functions

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related