I want to calculate all sum of all possible paths from root to leaf. Each node has value of an integer number (decimal).
In the following example:
1
/ \
2 4
/ /\
3 5 6
Possible paths are *123, 145, and 146, which adds to 414). In this example, 12 is not a valid path since 2 is not a leaf node.
I did basic tests and it works, and I'm wondering if the code is logically correct, and how I can improve its performance.
class Node:
def __init__(self, value, left, right):
self.value = value
self.left = left
self.right = right
def sum(node, prefix):
r1 = 0
r2 = 0
if not node:
return
if node and not node.left and not node.right:
return prefix*10+node.value
if node.left:
r1 = sum(node.left, prefix*10 + node.value)
if node.right:
r2 = sum(node.right, prefix*10 + node.value)
return r1+r2
if __name__ == "__main__":
node3 = Node(3, None, None)
node5 = Node(5, None, None)
node6 = Node(6, None, None)
node4 = Node(4, node5, node6)
node2 = Node(2, node3, None)
node1 = Node(1, node2, node4)
print sum(node1, 0)