CODEWITHSUNDEEP
pythonpython-3.xalgorithmrecursionbinary-tree
xarena
xarena

Reputation: 95

Sum all nodes of a n-ary tree in Python

I have a table in an excel file from this link:

enter image description here

How could I read it as an n-ary tree and sum up all nodes in Python if Input values are 1s? It would be better if it nodes and leaves names are also displayed on the tree.

         15
     /        \
    8          7
  /  \      /     \
  6   2    2       5
/ | \ |   /  \   / | \
3 3 0 2   2  0  0  2  3

Thanks a lot for your kind help at adavance.

My trial code:

class Node:
    def __init__(self, name, weight, children):
        self.children = children
        self.weight = weight
        self.weight_plus_children = weight

    def get_all_weight(self):
        if self.children is None:
            return self.weight_plus_children
        else:
            for child in self.children:
                # print(child)
                print("Child node score", child.get_weigth_with_children())
                self.weight_plus_children += child.get_weigth_with_children()

        return self.weight_plus_children

    def get_weigth_with_children(self):
        return self.weight_plus_children

leaf1 = Node('Evaluation item 1', 3, None)
leaf2 = Node('Evaluation item 2', 3, None)

leaf3 = Node('Evaluation item 3', 3, None)
leaf4 = Node('Evaluation item 4', 1, None)
leaf5 = Node('Evaluation item 5', 1, None)
leaf6 = Node('Evaluation item 6', 2, None)

leaf7 = Node('Evaluation item 7', 2, None)
leaf8 = Node('Evaluation item 8', 2, None)


subroot1 = Node('Ordinary account authentication', 0, [leaf1, leaf2])
subroot2 = Node('Public account identity verification', 0, [leaf3, leaf4, leaf5, leaf6])
subroot3 = Node('Platform equipment information record', 0, [leaf7, leaf8])

root1 = Node('User Management', 0, [subroot1, subroot2])
root2 = Node('Business platform deployment', 0, [subroot3])

root = Node('Business application security', 0, [root1, root2])

print(subroot1.get_all_weight())
print(subroot2.get_all_weight())
print(subroot3.get_all_weight())

print(root1.get_all_weight())
print(root2.get_all_weight())

print(root.get_all_weight())

Out:

Child node score 3
Child node score 3
6
Child node score 3
Child node score 1
Child node score 1
Child node score 2
7
Child node score 2
Child node score 2
4
Child node score 6
Child node score 7
13
Child node score 4
4
Child node score 13
Child node score 4
17

Upvotes: 1

Views: 1262

Answers (1)

Anmol Singh Jaggi
Anmol Singh Jaggi

Reputation: 8576

You can assign an integer to every node of the tree which will contain the sum of all children values recursively.

The inital value of each node will be 0.

Then you can run a recursive algorithm like this:

def sum_children(root):
    if root is None:
        return 0
    sum_total = 0
    for child in root.get_children():
        child_value = sum_children(child)
        if child_value > 0:
            sum_total += child_value
    root.value = sum_total
    return sum_total

# Call this function on the tree root
sum_children(tree_root)

Upvotes: 5

Related Questions