## Similar Problems

Similar Problems not available

# Sum Root To Leaf Numbers - Leetcode Solution

## Companies:

LeetCode: Sum Root To Leaf Numbers Leetcode Solution

Difficulty: Medium

Topics: tree binary-tree depth-first-search

The problem statement is:

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.

Example 1:

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, the sum is 12 + 13 = 25.

Example 2:

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, the sum is 495 + 491 + 40 = 1026.

Approach:

The problem can be solved by traversing the tree in a depth-first manner. We can keep track of the current number formed by adding the current node’s value to the number so far. If the current node is a leaf, we can add the current number to the total sum. Otherwise, we can recursively traverse the node’s left and right children, passing the current number as an argument.

Algorithm:

- Initialize a global variable sum and set it to 0.
- Define a helper function named dfs with parameters root and num.
- If root is null, return.
- If root is a leaf, add the current num to the sum by sum = sum + num*10 + root.val.
- Recursively call the dfs function for the left and right children of root, passing num*10+root.val as the updated value of num.
- Finally, call the dfs function for the root node with num = 0 to start the traversal from the root node.
- Return the sum.

Code:

class Solution { int sum = 0; // global variable to store sum public int sumNumbers(TreeNode root) { dfs(root, 0); // calling helper function with root and initial num as 0 return sum; }

```
public void dfs(TreeNode root, int num){
if(root == null){
return;
}
if(root.left==null && root.right==null){ // checking if node is leaf
sum += (num*10) + root.val; // adding the current num to the sum
return;
}
dfs(root.left, num*10 + root.val); //recursive call for left child
dfs(root.right, num*10 + root.val); //recursive call for right child
}
```

}

Time Complexity: The time complexity of the above algorithm is O(N), where N is the total number of nodes in the tree. This is because we are visiting each node once.

Space Complexity: The space complexity of the above algorithm is O(H), where H is the height of the tree. This is because the maximum number of recursive calls at any given time is equal to the height of the tree.

## Sum Root To Leaf Numbers Solution Code

`1`