CODEWITHSUNDEEP
pythonrecursiontree
BarTM
BarTM

Reputation: 57

Sum of nodes in a subtree (not binary)

I'm currently trying to find the sum of all nodes in a specified subtree. For example if I have a tree

     A(5)
     / \
   B(5) C(6)
   /    /  \
  D(3) E(3) F(7)
            |
            G(1)

and I want to know the the sum(C), which should return 17.

This is the code I came up with using recursion, but I can't seem to reach a subtree which has more than 2 levels. E.g. my algorithm doesn't seem to reach G. I'm trying to get better at recursion, but I can't seem to fix this. 

def navigate_tree(node,key): #node of the root of subtree, along with its key
    children = node.get_children()
    if (len(children) ==0):
        return node.key
    else:
        for child in children: #not a binary tree so trying to loop through siblings
            key += navigate_tree(child,key) #summing up key recursively
        return key

Upvotes: 2

Views: 844

Answers (2)

Ajax1234
Ajax1234

Reputation: 71451

You can use recursion with sum:

class Node:
  def __init__(self, n, v, c=[]):
    self.name, self.val, self.children = n, v, c

def get_sum(node):
   return node.val+sum(map(get_sum, node.children))

tree = Node('A', 5, [Node('B', 5, [Node('D', 3)]), Node('C', 6, [Node('E', 3), Node('F', 7, [Node('G', 1)])])])
print(get_sum(tree.children[-1]))

Output:

17

However, if you do not have access to the exact node C, you can apply a simple search as part of the recursive function:

def get_sum(t, node):
  def inner_sum(d, s=False):
     return d.val*(s or d.name == t)+sum(inner_sum(i, s or d.name == t) for i in d.children)
  return inner_sum(node)

print(get_sum('C', tree))

Output:

17

Upvotes: -1

quamrana
quamrana

Reputation: 39354

You would be better with an improved interface and being able to lean on the features of collections:

def navigate_tree(node): 
    children = node.get_children()
    key = node.key
    for child in children:
        key += navigate_tree(child)
    return key

# class Node and data A..G elided
print(navigate_tree(C))

Output:

17

The reason why your code appeared not to work, was that you were passing the previous key down to the next level of recursion. However, your code seemed to recurse OK. If you had added some print(node.key) you would have seen that you were visiting all the correct nodes.

Upvotes: 3

Related Questions