Problem with Depth First & Tree Traversals in c

Question

I am facing a problem related to dfs in C programming. I need to find Count Nodes Equal to Average of Subtree. Unfortunately, I did not find enough guides on c, so I am asking for help. This code still doesn't work and gives wrong results, so I'd appreciate it if you could point out my mistakes.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int ans=0;
int dfs(struct TreeNode* root){
    if (root == NULL) return 0,0;
    int left,left_count = dfs(root->left);
    int right,right_count = dfs(root->right);
    int totalSum = left+right+root->val;
    int count = left_count + right_count + 1;
    if (totalSum/count == root->val) ans++;
    return totalSum,count;
}

int averageOfSubtree(struct TreeNode* root){
    dfs(root);
    return ans;
}

I've modified this code many times, but I've never gotten to a working code. At the output, I get the data, but it is incorrect (thanks in advance).

Answer 1

Some issues:

• You seem to intend that your dfs function returns two int values, but this is not true. Your function is declared as returning int (one), and the comma operator will not return a tuple (like in Python), but will evaluate to the second argument.

  So return 0,0; has the same effect as return 0;

  And return totalSum,count; has the same effect as return count;

  And int left,left_count = dfs(root->left); will not initialise left, only left_count

  It is true that you need both the count and sum to be made available to the caller, and there are several ways you could do that. One is to pass pointers to int variables as arguments to dfs.

• As ans is global, and is not reset to 0, the tests on Leet Code will accumulate results from previous runs with the current run. It is better to avoid the global variable all together. Instead, you could make it the return value of dfs. Or also a pointer to a variable that is passed as argument...

Corrected version:

int dfs(struct TreeNode* root, int *count, int *sum){
    if (root == NULL) {
        *count = *sum = 0;
        return 0;
    }
    int left, left_count, right, right_count;
    int ans = dfs(root->left, &left_count, &left) + dfs(root->right, &right_count, &right);
    *sum = left + right + root->val;
    *count = left_count + right_count + 1;
    return ans + (*sum/(*count) == root->val);
}

int averageOfSubtree(struct TreeNode* root){
    int sum, count; // Dummy
    return dfs(root, &sum, &count);
}