Sum of nodes in a subtree (not binary)

Question

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

I think you meant: key += navigate_tree(child, child.key) [btw, why does the signature have node and key. Surely key is redundant?] — quamrana
– quamrana, Commented Mar 17, 2020 at 10:34
Yeah that makes sense. The reason i put "key" in the signature was so i could continue to add to the variable through the recursion process. I'm not too great at recursion so it probably was redundant. Thanks. — BarTM
– BarTM, Commented Mar 18, 2020 at 2:12

quamrana · Accepted Answer · 2020-03-17 10:43:56Z

3

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:

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.

answered Mar 17, 2020 at 10:43

quamrana

39.5k13 gold badges57 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

BarTM Over a year ago

Yeah i noticed that i was visiting all of the correct nodes, just never seemed to get the correct sum. It gets the correct output now, thanks. Guess ill have to practice recursion more.

Ajax1234 · Accepted Answer · 2020-03-17 15:32:37Z

-1

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:

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:

answered Mar 17, 2020 at 15:32

Ajax1234

71.7k9 gold badges67 silver badges110 bronze badges

Collectives™ on Stack Overflow

Sum of nodes in a subtree (not binary)

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related