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>assuming that your node class looks something like this:</p>

<pre><code>class Node:
    def __init__(self, value = 0, children = None):
        self.value = value
        self.children = [] if children is None else children
</code></pre>

<p>then this method should do the trick:</p>

<pre><code>def doesSumExist(startNode, targetSum, currentSum):
    if startNode is None:
        return False
    currentSum += startNode.value
    if currentSum == targetSum:
        return True
    for child in startNode.children:
        if doesSumExist(child, targetSum, currentSum):
            return True
    return False
</code></pre>

<p>Note that for this Node-class design the None-check of startNode isn't really necessary for the recursion but only for the entry point. So this would probably be better:</p>

<pre><code>def doesSumExist(startNode, targetSum):
    def inner(node, targetSum, currentSum):
        currentSum += node.value
        if currentSum == targetSum:
            return True
        #for people who like to save a few lines
        #return any(inner(child, targetSum, currentSum) for child in node.children)
        for child in node.children:
            if inner(child, targetSum, currentSum):
                return True
        return False

    if startNode is None:
        return False
    return inner(startNode, targetSum, 0)
</code></pre>

<p>Edit:
If you not only want to know if the sum exists in a path from your start node but also if it would exist in any given sub path this should work:</p>

<pre><code>def doesSumExist(startNode, targetSum):
    def inner(node, targetSum, allValues):
        allValues.append(node.value)
        currentSum = 0
        for val in reversed(allValues):
            currentSum += val
            if currentSum == targetSum:
                return True
        for child in node.children:
            if inner(child, targetSum, allValues):
                return True
        allValues.pop()
        return False

    if startNode is None:
        return False
    return inner(startNode, targetSum, [])
</code></pre>

python data-structures binary-tree