Check if a binary tree has a path equal to the given sum

I'm having an issue figuring out the solution for this problem:

"Given a binary tree (each node has an int value), and a sum, return 1 if the tree has a path equal to the given sum (from a node to a leaf, doesn't have to be the root), else return 0".

I've done a similar question, where the path has to start from the root. But here, the question states that the path can start anywhere, as long as it ends with a leaf..

Tried searching online for a solution, but I found some that are only working by using the buffer.

Is there any possible solution for this, without the buffer?

Thanks in advance!

(Prefer in C,C++ syntax or even a pseudo code ^.^``)

This was my first try:

int hasPathSum(Tree tr, int sum){
return hasPathSumRec(tr.root, sum, 0);
}


int hasPathSumRec(TNode* node, int sum, int current){

int num1, num2;
current += node->data;
if (current > sum)
    current = 0;

if (node->left == NULL && node->right == NULL){
    if (current == sum)
        return 1;
    return 0;
}
else if (node->left == NULL){
    return hasPathSumRec(node->right, sum, current);

}
else if (node->right == NULL){
    return hasPathSumRec(node->left, sum, current);
}
else{
    num1=hasPathSumRec(node->left, sum, current);
    num2=hasPathSumRec(node->right, sum, current);

    if (num1 > 0 || num2 > 0)
        return 1;
    else
        return 0;
}
}

and this was the second: (but it doesn't go through all of the nodes, so it's not good..)

int hasPathSum(Tree tr, int sum){
return hasPathSumRec(tr.root, sum, 0);
}

int hasPathSumRec(TNode* node, int sum, int current){
int num, num1, num2;


num = node->data;
current = num + current;

if (current > sum)
    current = num;


if (node->left == NULL && node->right == NULL){
    if (node->data == sum || current == sum)
        return 1;
    else
        return 0;
}
else if (node->left == NULL){
    num2 = node->right->data;
    if (current + num2 > sum)
        return hasPathSumRec(node->right, sum, num);

    else
        return hasPathSumRec(node->right, sum, current);

}
else if (node->right == NULL){
    num1 = node->left->data;
    if (current + num1 > sum)
        return hasPathSumRec(node->left, sum, num);
    else
        return hasPathSumRec(node->left, sum, current);

}
else{
    num1 = node->left->data;
    num2 = node->right->data;
    /LEFT SIDE--------------------------------------------------/
    if (current + num1 > sum)
        num2 = hasPathSumRec(node->left, sum, num);
    else
        num2 = hasPathSumRec(node->left, sum, current);
    /RIGHT SIDE--------------------------------------------------/
    if (current + num2 > sum)
        num1 = hasPathSumRec(node->right, sum,num);
    else
        num1 = hasPathSumRec(node->right, sum, current);


    if (num1 > 0 || num2 > 0)
        return 1;
    else
        return 0;
}

Solution

As you already mentioned, you compute the sum of a tree values as the sum of the sums of its subtrees plus the root value. It's clear that as soon as you can compute the sum of this tree you have computed the sums of all its subtrees. So the only thing left to do is adding a check if the sum is equal to the required one and return it. Here you can find an implementation for this idea and a Minimal, Complete, and Verifiable example, which you should have provided in the first place, saving people (me) the effort to write one.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _TNode {
    int data;
    struct _TNode *left, *right;
} TNode;

typedef struct {
    TNode *root;
} Tree;

typedef struct {
    int sum;
    bool found;
} hasPathSumRec_t;

hasPathSumRec_t hasPathSumRec(TNode* node, int sum)
{
    hasPathSumRec_t ret = { 0, false };
    if (!node)
        return ret;

    hasPathSumRec_t ret_left = hasPathSumRec(node->left, sum);
    hasPathSumRec_t ret_right = hasPathSumRec(node->right, sum);

    ret.sum = ret_left.sum + ret_right.sum + node->data;
    ret.found = ret_left.found || ret_right.found || ret.sum == sum;
    return ret;
}

int hasPathSum(Tree tr, int sum) {
    return hasPathSumRec(tr.root, sum).found;
}

int main(void)
{
    /*
    1 / 2 / 3 / *
      |   |   \ *
      |   \ 5 / * 
      |       \ *
      \ 4 / 6 / 7 / *
          |   |   \ *
          |   \ *
          \ 8 / *
              \ 9 / *
                  \ *
    */

    TNode n[] = {
        { 1, n + 4 - 1, n + 2 - 1 },
        { 2, n + 5 - 1, n + 3 - 1 },
        { 3, NULL, NULL },
        { 4, n + 8 - 1, n + 6 - 1 },
        { 5, NULL, NULL },
        { 6, NULL, n + 7 - 1 },
        { 7, NULL, NULL },
        { 8, n + 9 - 1, NULL },
        { 9, NULL, NULL },
    };

    Tree t = { n };

    int tests[] = { 8, 9, 10, 12, 13, 17 };
    size_t ntests = sizeof tests / sizeof *tests;
    for (size_t i = 0; i < ntests; ++i)
        printf("%i - %i\n", tests[i], hasPathSum(t, tests[i]));
}

Further improvements could allow an early exit if sum is found or exceeded.