Sum Root to Leaf Numbers
Leetcode Daily Challenge (14th March, 2023)
Problem Statement:-
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
- For example, the root-to-leaf path
1 -> 2 -> 3represents the number123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Link: https://leetcode.com/problems/sum-root-to-leaf-numbers/
Problem Explanation with examples:-
Example 1
Input: root = [1,2,3,7,3,null,0,1,4,null,9,6,5]
Output: 6395
Explanation:
The root-to-leaf path 1->2->7->1 represents the number 1271.
The root-to-leaf path 1->2->7->4 represents the number 1274.
The root-to-leaf path 1->2->3->9 represents the number 1239.
The root-to-leaf path 1->3->0->6 represents the number 1306.
The root-to-leaf path 1->3->0->5 represents the number 1305.
Therefore, sum = 1271 + 1274 + 1239 + 1306 + 1305 = 6395.
Example 2
Input: root = [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.
Example 3
Input: root = [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.
Constraints
The number of nodes in the tree is in the range
[1, 1000].0 <= Node.val <= 9The depth of the tree will not exceed
10.
Intuition:-
First of all, we need to find all the root-to-leaf paths and store them somewhere as numbers.
Then we need to add all the numbers and return the sum.
As it's a binary tree problem we need to use recursion to solve it.
We need to use a helper function that will return all the leaf paths from itself.
At each level, we can have a list of all the paths from that level to the leaves.
We can use a list to store all the paths and then convert them to numbers and add them to get the sum.
Solution:-
We can use a helper function to solve the problem.
Our helper function will take a node as input and return a list of all the paths from that node to the leaves.
For this, we will use recursion.
We will have a base case where if the node is null we will return an empty list.
Then initialize an empty list to store all the paths.
Then we will call the helper function on the left and right child of the node.
Now check if the left return list is not empty.
If not empty then we will add the node value to each of the paths in the list and append it to the list.
Then we will do the same for the right child.
If both the left and right child returns empty lists then we will append the node value to the list.
Now we will return the list.
Finally, we will call the helper function on the root node and store the result in a variable.
Then we will convert the list of strings to a list of integers.
Return the sum of the list.
Solution explanation:-
Example 1
Input: root = [1,2,3,7,3,null,0,1,4,null,9,6,5]
Output: 6395
Explanation:
The root-to-leaf path 1->2->7->1 represents the number 1271.
The root-to-leaf path 1->2->7->4 represents the number 1274.
The root-to-leaf path 1->2->3->9 represents the number 1239.
The root-to-leaf path 1->3->0->6 represents the number 1306.
The root-to-leaf path 1->3->0->5 represents the number 1305.
Therefore, sum = 1271 + 1274 + 1239 + 1306 + 1305 = 6395.
Example 2
Input: root = [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.
Example 3
Input: root = [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.
Code:-
JAVA Solution
class Solution {
public int sumNumbers(TreeNode root) {
List<String> x = solve(root);
List<Integer> y = new ArrayList<Integer>();
for (String i : x) {
y.add(Integer.parseInt(i));
}
int sm = 0;
for (int i : y) {
sm += i;
}
return sm;
}
public List<String> solve(TreeNode node) {
if (node == null) {
return new ArrayList<String>();
}
List<String> arr = new ArrayList<String>();
List<String> left = solve(node.left);
List<String> right = solve(node.right);
if (left.size() != 0) {
for (String i : left) {
arr.add(String.valueOf(node.val) + i);
}
}
if (right.size() != 0) {
for (String i : right) {
arr.add(String.valueOf(node.val) + i);
}
}
if (left.size() == 0 && right.size() == 0) {
arr.add(String.valueOf(node.val));
}
return arr;
}
}
Python Solution
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def solve(node):
if not node:
return []
arr = []
left = solve(node.left)
right = solve(node.right)
if len(left) != 0:
for i in left:
arr.append(str(node.val)+i)
if len(right) != 0:
for i in right:
arr.append(str(node.val)+i)
if len(left)== 0 and len(right) == 0:
arr.append(str(node.val))
return arr
x = solve(root)
y = []
for i in x:
y.append(int(i))
sm = sum(y)
return sm
Complexity Analysis:-
TIME:-
Time complexity is O(N) where N is the total number of nodes in the binary tree. This is because the solve function is called once for each node in the tree, and each call takes O(1) time for nodes with no children and O(N) time for nodes with two children, due to the for loops that iterate over the left and right subtrees. The conversion of string to integer and the summation of the resulting list of integers takes O(N) time as well.
SPACE:-
Space complexity of this code is also O(N), due to the space used by the arr list in the solve function. In the worst case, where the binary tree is a linear chain, the arr list will contain N strings of length N, which requires O(N^2) space. However, in most cases, the arr list will contain fewer than N strings, so the space complexity is O(N).