Given a binary tree, where every node value is a Digit from 1-9 .Find the sum of all the numbers which are formed from root to leaf paths.

For example consider the following Binary Tree.

There are 4 leaves, hence 4 root to leaf paths:

Answer = 632 + 6357 + 6354 + 654 = 13997

The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus node’s data.

# Python program to find sum of all paths from root to leaves
# A Binary tree node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Returs sums of all root to leaf paths. The first parameter is root
# of current subtree, the second paramete"r is value of the number
# formed by nodes from root to this node
def treePathsSumUtil(root, val):
# Base Case
if root is None:
return 0
# Update val
val = (val*10 + root.data)
# If current node is leaf, return the current value of val
if root.left is None and root.right is None:
return val
# Recur sum of values for left and right subtree
return (treePathsSumUtil(root.left, val) +
treePathsSumUtil(root.right, val))
# A wrapper function over treePathSumUtil()
def treePathsSum(root):
# Pass the initial value as 0 as ther is nothing above root
return treePathsSumUtil(root, 0)
# Driver function to test above function
root = Node(6)
root.left = Node(3)
root.right = Node(5)
root.left.left = Node(2)
root.left.right = Node(5)
root.right.right = Node(4)
root.left.right.left = Node(7)
root.left.right.right = Node(4)
print "Sum of all paths is", treePathsSum(root)

Time Complexity: The above code is a simple preorder traversal code which visits every exactly once. Therefore, the time complexity is O(n) where n is the number of nodes in the given binary tree.