I have this function that checks if the sum of the keys of the paths from a node to a leaf is always lower than a certain value k and if that's not the case a flag is set to 1 to keep track of that.

Is it possible to make this function of type int or bool and make it return 0 if sum is always < than k and 1 if there is a case where sum >= k without using a flag like I'm doing?

int flag=0;
void checkSum(Node node,int sum,int k){
    if(node==nullptr){
        return;
    } 
    sum=sum node->key;
    if(node->left==nullptr && node->right==nullptr){
        if(sum>=k){
            flag=1;
        }
        return;
    }
    checkSum(node->left,sum,k);
    checkSum(node->right,sum,k);
    
}

CodePudding user response：

How about:

bool checkSum(Node *node, int sum, int k){
    if (node == nullptr) return true;
    sum  = node->key;
    if (sum >= k) return false;
    return checkSum(node->left, sum, k) && checkSum(node->right, sum, k);
}

If you made it to a nullptr without returning false and therefore without exceeding k along the path, you can return true back up to the caller. If at any point sum exceeds k you can return false, which will short-circuit further recursive calls and propagate all the way back to the root because of the && operator. So the tree gets explored in a dfs fashion and returns false back up to the root anytime a pathsum exceeds k, otherwise it returns true.

However, this implementation was assuming non-negative node keys. If this cannot be assumed, such that you really only want to check sum at leaf nodes, you could amend it as:

bool checkSum(Node *node, int sum, int k) {
    if (!node->left && !node->right)
        return sum < k;
    sum  = node->key;
    return checkSum(node->left, sum, k) && checkSum(node->right, sum, k);
}