Problem: https://leetcode.com/problems/sum-root-to-leaf-numbers/
Solution Explanation Blog Post: https://medium.com/leetcode-solutions/summing-root-to-leaf-numbers-in-a-binary-tree-353f33c8565e
Solution Explanation Text:
Summing Root to Leaf Numbers in a Binary Tree
Sum Root to Leaf Numbers is an interesting problem from Leetcode. The problem is of medium difficulty and is about binary trees. This post presents and explains the solution along with the thought process.
I assume that youโre familiar with Python and the concept of binary trees. If youโre not, you can read this article to get started.
The Problem
Given a binary tree whose nodes contain values 0-9, we have to find the sum of all numbers formed by root-to-leaf paths. A leaf is a node that doesnโt have any child nodes. In a binary tree, a root-to-leaf path is always unique. Here below is the expected behavior of the solution required:
In the tree on the left, the output is 25. 25 is the sum of 12 and 13, which are the two numbers formed when starting from 1 and visiting every leaf. In the tree on the right, the output is 1026 as it is sum of the three numbers 495, 491 and 40.
The Observations and Insights
-
We notice that we traverse the tree from the root to the leaf, visiting some leaves before many of the direct children of the root itself. This suggests that a depth-first search might be more useful here, and especially the one which starts visits the root first.
-
We notice that the building of numbers is incremental and similar of sorts: the only difference between 495 and 491 is the last digit. If we remove the 5 and insert a 1 in its place, we have the next number. A number is essentially made of up all digits in its ancestor nodes and thus shares many digits with siblings and nodes within the same sub-tree.
-
Finally, we notice that this problem involves a tree so a recursive solution is possible and natural.
The Solution
We can do a pre-order traversal of the tree where we incrementally build up a number and exploit the fact that numbers formed by nodes in the same sub-tree have common digits for common ancestors. When weโre done forming numbers in a sub-tree, we can back-track and go to another sub-tree.
Letโs create a Solution class to encompass our solution. We can have an array attribute to store all the root-to-leaf numbers formed and an array attribute to store the current list of digits as we traverse the tree.
class Solution:
curr = [] # stores digits in the current path
numbers = [] # stores numbers formed by root-to-leaf paths
def sum_numbers(self, root: TreeNode) -> int:
The method signature given to us in the problem has one argument: root , which is of the type TreeNode . A TreeNode class is as follows (from Leetcode):
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
As highlighted earlier, we need to build a number for each root-to-leaf path so that we can compute the sum of all numbers. To keep our code modular, letโs define another method to do this (instead of doing it within the sum_numbers method). This method will be responsible for filling our numbers array with all the root-to-leaf numbers. Letโs call it get_root_to_leaf_nums. It should take an argument of type TreeNode as well and return nothing (since it is modifying state by filling up the numbers array.
Our Solution class looks like:
class Solution:
curr = []
numbers = []
def sum_numbers(self, root: TreeNode) -> int:
def get_root_to_leaf_nums(self, root: TreeNode):
We can think of the get_root_to_leaf_nums method recursively and process each node differently based on whether it is a leaf or a not a leaf.
-
If it is a leaf, we want to add the value to our curr array, create a number based on the digits in the curr array and add the number to the numbers array. Since the node is a leaf, we will backtrack from here to the previous node and therefore want to delete the current nodeโs value from the curr array.
-
If it is not a leaf, we want to add the value to our curr array, and then continue traversing the left and right sub-trees. When done, we want to remove the current nodeโs value from the curr array as we backtrack.
Thus, our get_root_to_leaf_nums method will be as follows:
def get_root_to_leaf_nums(self, root: TreeNode):
if root:
self.curr.append(str(root.val))
if not root.left and not root.right:
self.numbers.append(self.convert_to_num(self.curr))
self.curr.pop()
else:
self.get_root_to_leaf_nums(root.left)
self.get_root_to_leaf_nums(root.right)
self.curr.pop()
We check if the root is not a None and simply do nothing if it is None as we are not concerned with empty sub-trees. We need a convert_to_num method that can convert the curr array representing digits of the number to an integer:
def convert_to_num(self, arr) -> int:
cum = int("".join([str(x) for x in arr]))
return int(cum)
We basically convert each int in the curr array to a string, concatenate the string and then typecast the result back to an int.
Now, in our main method, we first want to fill the numbers array and then simply return its sum. We need to clear the numbers array at the end because Leetcode will typically run this through a lot of testcases and subsequent testcases will fail if the numbers array contains solutions numbers from a previous testcase.
Finally, this is how our solution looks:
class Solution:
curr = []
numbers = []
def sum_numbers(self, root: TreeNode) -> int:
#get all numbers from root to leaf paths
self.pre_order(root)
# sum all numbers
ans = sum(self.numbers)
self.numbers.clear()
return ansdef get_root_to_leaf_nums(self, root: TreeNode):
if root:
self.curr.append(str(root.val))
if not root.left and not root.right:
self.numbers.append(self.convert_to_num(self.curr))
self.curr.pop()
else:
self.get_root_to_leaf_nums(root.left)
self.get_root_to_leaf_nums(root.right)
self.curr.pop()def convert_to_num(self, arr) -> int:
cum = int("".join([str(x) for x in arr]))
return int(cum)
The Algorithmic Complexity
When solving a problem, it is important to analyze its algorithmic complexity not only to estimate its performance but also to identify areas for improvement and reflect on our problem solving skills.
Time:
Our solution is a modification of the depth-first-search pre-order traversal where we visit all nodes exactly once. Thus, our runtime is simply O(N) where N represents the number of nodes in the given tree. I canโt think of a solution that will be better than O(N) because to construct a number from digits, I need to know all the digits.
We also incur a small cost to sum the numbers in the numbers list and to convert the curr array to an integer, but these costs are insignificant when compared to the cost of visiting each node (the number of numbers formed will be less than total number of nodes).
Space:
In terms of storage, we store the numbers formed and the current list of digits, which is not that significant. However, what is significant is the recursion call stack that builds up as our get_root_to_leaf_nums calls itself. These calls โbuild-upโ as one waits for another to finish.
Generally, the maximum call stack will be 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. In the worst case, the binary tree is skewed in either direction and thus H = N. Therefore, the worst case space complexity is O(H).
You can read this article to know more about recursion call stacks.
The Conclusion
I hope this post helped! Please do let me know if you have any feedback, comments or suggestions by responding to this post.
![[RFC] Community driven interview question bank](https://avatars.githubusercontent.com/u/66356390?v=4)
![[RFC] Technical Handbook Offers Repo](https://avatars.githubusercontent.com/u/77266823?v=4)
![[RFC] Community-powered Resume Review Portal](https://avatars.githubusercontent.com/u/35712975?v=4)
