Sum of Root to Leaf Paths

We have been given a binary tree consisting of nodes with digit values.

We need to take in account of every possible root-to-leaf path.

Each of these path represent a number. We have to effectively return the total sum of all the number represented by each of these paths.

This is the order of the tree and how the sum is calculated from root to leaf paths

• We will be starting at the root with current number curr = 0.
• Every time when the current node’s digit appended to curr from root to leaf and we will be recursing to left and right child.
• When we reach the leaf node (a node that doesn’t have any left or right child), we will be forming complete root-to-leaf number. Then we will add Curr to overall Number.

Python Code as follows.

So, what’s the time and space complexity?

The time complexity comes down to O(N), where N is the number of nodes of the tree.

O(H) is the width of the tree, where H is the maximum depth of tree.