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)