How to check whether the sum exists for a given path in a tree
<p>I want to check if the sum of values in any path from the start node to the </p>

<p>leaf node exists.</p>

<p>For example suppose I have startNode is say a 7 and the sumTarget is 15 if the tree is: </p>

<pre><code>        a-7
  b - 1    e- 8
  c - 2    
  d -9 
</code></pre>

<p>Then since 7 +8 equals 15 it would return true</p>

<p>If I have b as the startNode and 12 as the sumTotal then it would also return true because 1 +2 + 9 is 12 starting with b. </p>

<pre><code>class Node {
    int value;
    Node [] children
}
</code></pre>

<p>I don't think this is right, but I'm not sure what is wrong. </p>

<pre><code>def doesSumExist(startNode, sumTarget, currentSum):
    totalSum = sumTarget
    if startNode is not Null:
        if totalSum + startNode.value == sumTarget:
            return True
        else:
            totalSum += startNode.value
    else:
        Node startNode = doesSumExist(startNode.left, sumTarget, currentSum)  
        if startNode is not Null:
            return currentSum
        startNode = doesSumExist(startNode.right, sumTarget,currentSum)
    return False
</code></pre>

<p>In that case I think what you're searching for is something like the following:</p>

<pre><code>def doesSumExist(startNode, sumTarget, currentSum):
    totalSum = currentSum
    if startNode is not Null:
        if totalSum + startNode.value == sumTarget: #If this node completes the sum
            return True
        else: #if not
            totalSum += startNode.value #increase current sum
    if doesSumExist(startNode.left, sumTarget, totalSum): #recursive starting on the left children
        return True
    elif doesSumExist(startNode.right, sumTarget, totalSum): #recursive starting on the right children
        return True           
    return False #if the sum is not present (starting in startNode).
</code></pre>

<p>However, this does not check if any successive combination of nodes contains the sum (the code would much more complex).</p>

<p>Hope this helps</p>

python data-structures binary-tree