C++: How do I count the number of nodes in a binary tree for which its value module its height is minor to 2?

Question

I'm trying to implement a function which counts the nodes in a binary tree that respect the following condition: ( node->value % height )<2 I know it must be a recursive function and I tried to implement it as it follows:

    int count(Node* tree, int h=1){
       if (!tree) return 0;

       if ((tree->value%h)<2)
          return count(tree->left, h++) + count(tree->right, h++) + 1;
       else
          return count(tree->left, h++) + count(tree->right, h++);
    }

This function doesn't work and I can't understand where my mistake is. I'll appreciate any help you can give me. Thanks in advance.

Answer 1

With the statement

return count(tree->left, h++) + count(tree->right, h++) + 1;

you are incrementing h, which means that one of the calls to count might go with a higher value than the other one. Actually it is undefined behaviour, since the order of evaluation of the two h++ is not defined.

Write...

return count(tree->left, h+1) + count(tree->right, h+1) + 1;