How to Solve Sum Root to Leaf Numbers
Sum Root to Leaf Numbers Introduction
Sum Root to Leaf Numbers Introduction
The Sum Root to Leaf Numbers problem asks us to return the total sum of all root-to-leaf numbers. This problem requires us to traverse the tree using depth-first search and keep track of the current sum, adding the number from each leaf node we come across.
Sum Root to Leaf Numbers Problem
Sum Root to Leaf Numbers Problem
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.
Example Inputs and Outputs
Example 1
Input: Input: root = [1,2,3]
Output: 25
Example 2
Input: root = [4,9,0,5,1]
Output: 1026
Sum Root to Leaf Numbers Solutions
Sum Root to Leaf Numbers Solutions
To solve this problem, we can use a depth-first search (DFS) approach to traverse the binary tree. We can keep track of the current sum, which represents the number that is formed by the path from the root to the current node. If we get to a leaf node, we add the current sum to the total sum. Otherwise, we can recursively traverse the left and right subtrees, updating the current sum along the way. Finally, we return the total sum as the result.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sumNumbers(self, root):
def dfs(node, currSum):
if not node:
return 0
# Calculate the current number by appending the node's value to the current sum
currSum = currSum * 10 + node.val
# If it's a leaf node, return the current number
if not node.left and not node.right:
return currSum
# Recursively traverse the left and right subtrees, passing the updated current number
leftSum = dfs(node.left, currSum)
rightSum = dfs(node.right, currSum)
# Return the sum of both left and right subtree sums
return leftSum + rightSum
return dfs(root, 0)
# Create the binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# Call the sumNumbers function and print the result
solution = Solution()
result = solution.sumNumbers(root)
print("Sum of numbers in the binary tree:", result)1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def sumNumbers(self, root):
9 def dfs(node, currSum):
10 if not node:
11 return 0
12
13 # Calculate the current number by appending the node's value to the current sum
14 currSum = currSum * 10 + node.val
15
16 # If it's a leaf node, return the current number
17 if not node.left and not node.right:
18 return currSum
19
20 # Recursively traverse the left and right subtrees, passing the updated current number
21 leftSum = dfs(node.left, currSum)
22 rightSum = dfs(node.right, currSum)
23
24 # Return the sum of both left and right subtree sums
25 return leftSum + rightSum
26
27 return dfs(root, 0)
28
29# Create the binary tree
30root = TreeNode(1)
31root.left = TreeNode(2)
32root.right = TreeNode(3)
33root.left.left = TreeNode(4)
34root.left.right = TreeNode(5)
35
36# Call the sumNumbers function and print the result
37solution = Solution()
38result = solution.sumNumbers(root)
39print("Sum of numbers in the binary tree:", result)Time/Space Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes in the binary tree. We visit each node exactly once during the depth-first search traversal.
- Space Complexity: O(H), where H is the height of the binary tree. In the worst case, the recursion stack can grow up to the height of the tree.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
