Sum Root To Leaf Numbers

Problem Statement

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Sample Test Case

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Problem Solution

    1
   / \
  2   3

This is a simple tree traversal problem.

Every time, we go from a node to a child node, we pass the path sum of the parent. When we visit the node, we calculate the new path sum.

When we reach a leaf node, we add the calculated path sum to our tree sum.

For our example, at the root node, the node value is 1, so we set the path sum as 1 and pass it to the child node on left. We do not touch our tree sum.

When we reach the child node 2, we take the path from the parent, multiply by 10 and add the current node value. This will just append the node value at the end of the path sum. So, we calculate the path sum as 1*10+2, ie, 12.

We know 2 is a leaf node. We know it is a leaf node, as it has no left or right children. So we add the new path sum to our tree sum.

So now, our path sum is 12, and our tree sum is 12 .

Now, we backtrack back and explore the right node. We know the path sum at node 1 is 1. We pass that to node 3.

Now, when we reach the child node 3,we append 3 to our path sum using the same logic we followed earlier, and make the path sum 13.

As we know 3 is a leaf node, we add the new path sum to our tree sum.

So now, our path sum is 13, and our tree sum is 12 + 13 = 25.

Now, we have traversed our entire tree. Our tree sum is 25.

Complexity Analysis

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.

Space Complexity: The maximum call stack is dependent upon the height of the binary tree (since we start backtracking after we visit a leaf), giving a complexity of O(H) where H is the height of the binary tree.

Code Implementation

• C++
• Java
• Python

#include <bits/stdc++.h>
using namespace std;

class node
{
    public:
    int data;
    node *left, *right;
};

// function to allocate new node with given data
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = Node->right = NULL;
    return (Node);
}

// Returns sum of all root to leaf paths.
// The first parameter is root
// of current subtree, the second
// parameter is value of the number formed
// by nodes from root to this node
int treePathsSumUtil(node *root, int val)
{
    // Base case
    if (root == NULL) return 0;

    // Update val
    val = (val*10 + root->data);

    // if current node is leaf, return the current value of val
    if (root->left==NULL && root->right==NULL)
    return val;

    // recur sum of values for left and right subtree
    return treePathsSumUtil(root->left, val) +
        treePathsSumUtil(root->right, val);
}

// A wrapper function over treePathsSumUtil()
int treePathsSum(node *root)
{
    // Pass the initial value as 0
    // as there is nothing above root
    return treePathsSumUtil(root, 0);
}

// Driver code
int main()
{
    node *root = newNode(6);
    root->left = newNode(3);
    root->right = newNode(5);
    root->left->left = newNode(2);
    root->left->right = newNode(5);
    root->right->right = newNode(4);
    root->left->right->left = newNode(7);
    root->left->right->right = newNode(4);
    cout<<treePathsSum(root);
    return 0;
}

public class TreeNode
{
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) 
    { 
        this.val = val; 
    }

    public int treePathsSum(TreeNode root) 
    {
        return dfs(root, 0);
    }
    
    
    int dfs(TreeNode node, int path) 
    {
        if (node == null) 
            return 0;
    
        path = path*10 + node.val;
        
        if (node.left == null && node.right == null) 
            return path;
    
        return dfs(node.left, path) + dfs(node.right, path);
    }
    
    public static void main(String[] args) 
    {
       TreeNode t = new TreeNode(6);
        t.left = new TreeNode(3);
        t.right = new TreeNode(5);
        t.left.left = new TreeNode(2);
        t.left.right = new TreeNode(5);
        t.right.right = new TreeNode(4);
        t.left.right.left = new TreeNode(7);
        t.left.right.right = new TreeNode(4);

        System.out.println(t.treePathsSum(t));
        
    }    
}

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def sumNumbers(root):
    def dfs(node, val):
        
        if not node: 
            return 0
            
        val = val*10 + node.val
        if not (node.left or node.right): 
            return val
            
        return dfs(node.left, val) + dfs(node.right, val)
        
    return dfs(root, 0)
    
t = TreeNode(6)
t.left = TreeNode(3)
t.right = TreeNode(5)
t.left.left = TreeNode(2)
t.left.right = TreeNode(5)
t.right.right = TreeNode(4)
t.left.right.left = TreeNode(7)
t.left.right.right = TreeNode(4)

print(sumNumbers(t))