# Sum Root to Leaf Numbers ### **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 -> 3` represents the number `123`. 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/](https://leetcode.com/problems/sum-root-to-leaf-numbers/) ### **Problem Explanation with examples:-** **Example 1** ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1678805917120/0c24af5b-0929-49c7-b2b5-14ac62edaf73.jpeg align="center") ```markdown 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** ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1678806027458/9ff77a27-ade9-4fdd-9c28-c9637aa8db0c.jpeg align="center") ```markdown 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** ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1678806014499/aafa5b1e-b52e-416c-9389-9ea81ccdad69.jpeg align="center") ```markdown 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 <= 9` * The 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** ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1678806521181/77eef06b-2e2e-4ccd-969d-aa9a8eeab457.png align="center") ```markdown 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** ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1678806587137/1680c7e6-2a2b-4662-b648-7e7ef7a3644d.png align="center") ```markdown 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** ![](https://cdn.hashnode.com/res/hashnode/image/upload/v1678806607569/d9d44bc9-aab5-415a-8979-2faab7041050.png align="center") ```markdown 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 ```java class Solution { public int sumNumbers(TreeNode root) { List x = solve(root); List y = new ArrayList(); for (String i : x) { y.add(Integer.parseInt(i)); } int sm = 0; for (int i : y) { sm += i; } return sm; } public List solve(TreeNode node) { if (node == null) { return new ArrayList(); } List arr = new ArrayList(); List left = solve(node.left); List 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 ```python 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). ### References:- * [**Recursion**](https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/) * [**Binary Tree**](https://www.geeksforgeeks.org/binary-tree-data-structure/) ### Connect with me:- * [**Twitter**](https://twitter.com/lakshit_cs) * [**Github**](https://github.com/Lakshit-Chiranjiv) * [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)