-
-
Notifications
You must be signed in to change notification settings - Fork 14.6k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add solution to a leetcode problem. #165
Comments
Hey @raivatshah, what is this supposed to be? Are you trying to contribute to the handbook? If so, please open a pull request rather than an issue. That said, as with the rest of the algorithmic content in the handbook, it is probably unnecessary for such a verbose walkthrough of a relatively simple tree question. It also seems like all the content here was pasted over from your linked medium post. Are you just trying to cross-post your article here for visibility? |
For context, I asked him to create an issue and I'll make the PR. The website doesn't have
a blog now
…On Fri, May 22, 2020, 3:04 PM Louie Tan ***@***.***> wrote:
Closed #165
<#165>.
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<#165 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAKBCHKUEGRJTDKN65UUPNTRSYPYNANCNFSM4NHQU2ZA>
.
|
Ah got it. Btw @raivatshah I just took a look at the solution writeup and I think there are some gaps.
|
Closed via #166 |
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 of12
and13
, which are the two numbers formed when starting from1
and visiting every leaf. In the tree on the right, the output is1026
as it is sum of the three numbers495
,491
and40
.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
and491
is the last digit. If we remove the5
and insert a1
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.The method signature given to us in the problem has one argument: root , which is of the type
TreeNode
. ATreeNode
class is as follows (from Leetcode):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 itget_root_to_leaf_nums
. It should take an argument of typeTreeNode
as well and return nothing (since it is modifying state by filling up thenumbers
array.Our
Solution
class looks like: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 thecurr
array and add the number to thenumbers
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 thecurr
array as we backtrack.Thus, our
get_root_to_leaf_nums
method will be as follows:We check if the root is not a
None
and simply do nothing if it isNone
as we are not concerned with empty sub-trees. We need aconvert_to_num
method that can convert thecurr
array representing digits of the number to an integer:We basically convert each
int
in thecurr
array to astring
, concatenate the string and then typecast the result back to anint
.Now, in our main method, we first want to fill the
numbers
array and then simply return its sum. We need to clear thenumbers
array at the end because Leetcode will typically run this through a lot of testcases and subsequent testcases will fail if thenumbers
array contains solutions numbers from a previous testcase.Finally, this is how our solution looks:
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)
whereN
represents the number of nodes in the given tree. I can’t think of a solution that will be better thanO(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 thecurr
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)
whereH
is the height of the binary tree. In the worst case, the binary tree is skewed in either direction and thusH = N
. Therefore, the worst case space complexity isO(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.
The text was updated successfully, but these errors were encountered: