CODEWITHSUNDEEP
pythondata-structuresbinary-tree
Sam
Sam

Reputation: 17

How to check whether the sum exists for a given path in a tree

I want to check if the sum of values in any path from the start node to the

leaf node exists.

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

        a-7
  b - 1    e- 8
  c - 2    
  d -9

Then since 7 +8 equals 15 it would return true

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. 

class Node {
    int value;
    Node [] children
}

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

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

Upvotes: 0

Views: 208

Answers (2)

Velocirobtor
Velocirobtor

Reputation: 386

assuming that your node class looks something like this:

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

then this method should do the trick:

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

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:

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)

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:

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, [])

Upvotes: 1

luizfvpereira
luizfvpereira

Reputation: 348

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

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).

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

Hope this helps

Upvotes: 1

Related Questions