Size of Binary Tree: wrong result when submitting code to online judge

Question

I was trying to solve GeeksForGeeks problem Size of Binary Tree:

Given a binary tree of size N, you have to count number of nodes in it. For example, count of nodes in below tree is 4.

      1
     / \
   10   39
  /
 5

Unfortunately for the test case below I'm getting "incorrect answer" on my recursive code. Can someone tell me where I'm going wrong?

Input:
2 // Number of test cases
1 2 3 // Test Case #1
10 5 9 N 1 3 6  // Test Case #2

My Output: 
3
9

Expected Output: 
3
6

My Code:

/* Tree node structure  used in the program
 struct Node
 {
     int data;
     Node* left;
     Node* right;
}; */

/* Computes the number of nodes in a tree. */

int nodes=0;

void dfs(Node* node) {
    if (node==NULL) return;
    ++nodes;
    // cout << node->data << " ";
    dfs(node->left);
    dfs(node->right);
}

int getSize(Node* node)
{
   // Your code here
   dfs(node);
   return nodes;
}

Answer 1

The mistake is that your code has a global int nodes that is only initialised once. When getSize is called multiple times, then only at the first call you can be sure it really is zero. All other calls will just keep incrementing that counter without it having been reset.

So either reset that counter just before the call to dfs is made, or -- better -- redesign your code so that you don't need a global counter at all, for example by having dfs return a counter. And if you do that, you can even make getSize recursive itself, without any need of a separate dfs function.

NB: don't use NULL in C++, but nullptr.

Here is a spoiler solution:

int getSize(Node* node) { if (node==nullptr) return 0; return 1 + getSize(node->left) + getSize(node->right); }