Summing Root To Leaf Numbers

S7rthak
S7rthak
Jul 29, 2020 · 5 min read
Photo by Chris Ried on Unsplash

Sum Root to Leaf Numbers is an interesting problem from LeetCode. The problem is of medium difficulty and is about binary trees. This post is an explained solution to the problem.

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 the sum of the three numbers 495, 491 and 40.

The Observations and Insights

  1. To construct a number, we traverse the tree from the root to the leaf, appending digits where the most significant digit is at the root, and the least significant digit is at the leaf. We visit some leaves before other nodes that are closer to the root. This suggests that a depth-first search will be useful.
  2. The construction of numbers is incremental and similar of sorts: the only difference between 495 and 491 (from the tree on the right) is the last digit. If we remove the 5 and insert a 1 in its place, we have the next required number. A number essentially comprises of the leaf's digit appended to all the digits in ancestor nodes. Thus, numbers within the same subtree have common digits.
  3. Finally, notice that this problem involves a tree, so a recursive solution is helpful.

The Solution

We can do a pre-order traversal of the tree where we incrementally construct a number and exploit the fact that numbers formed by nodes in the same sub-tree have common digits. When we’re done forming numbers in a sub-tree, we can backtrack and go to another sub-tree.

Let’s create a Solution class to encompass our solution.

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):

From observation #2, notice that appending a node’s digit to its ancestors can be achieved by moving all the digits of the number formed by ancestors to the right by 1 place and adding the current node’s digit. The digits can be moved by multiplying the number formed by ancestors by 10 (since we’re in base-10). For example:

495 = 49 x 10 + 5

Thus, we can keep track of the current digits in an integer. This is important because we won’t incur extra storage space for higher input sizes. We can pass around this value in the function parameter itself. Since the method signature given can only have one parameter, let’s create a sum_root_to_leaf_helper method.

We can think of the sum_root_to_leaf_helper method recursively and process each node differently based on whether or not it is a leaf.

  • If the node is a leaf, we want to add its digit to our current digits by moving all the other digits to the right. We also want to return this value (since we’ll backtrack from here).
  • If it is not a leaf, we want to add the digit to our current digits by moving all the other digits to the right. We also want to continue constructing the number by traversing down this node’s left and right subtrees.

If the current node is a None, we can simply return 0 because it doesn't count.

Thus, our sum_root_to_leaf_helper method will be as follows:

We use a default value for the partial sum to be 0.

In our main method, we want to include the sum_root_to_leaf_helper method as a nested method and simply pass on the node parameter. Finally, this is how our solution looks:

The Algorithmic Complexity

When we come up with a solution, 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. We should always ask the question: can we do better than X? Where X is the current complexity of our solution.

Time:

Our solution is a modification of the depth-first-search pre-order traversal where we visit all nodes exactly once and perform a trivial computation (moving digits by integer multiplication). Thus, our runtime is simply O(N) where N represents the number of nodes in the given tree. A solution better than O(N) doesn't seem possible because to construct a number from digits, we need to know all the digits (and thus visit all nodes).

Space:

In terms of storage, we incur a high cost in the recursion call stack that builds up as our sum_root_to_leaf_helper calls itself. These calls build-up as one waits for another to finish.

The maximum call stack is 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(N).

You can read this article to know more about recursion call stacks.

It is possible to do better than O(N) by using a Morris Preorder Traversal. The basic idea is to link a node and its predecessor temporarily. You can read more about it here.

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.

Weekly Webtips

Explore the world of web technologies through a series of tutorials

Sign up for 💌 Weekly Newsletter

By Weekly Webtips

Get the latest news on the world of web technologies with a series of tutorial Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

S7rthak

Written by

S7rthak

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Codeforces(Expert)

Weekly Webtips

Explore the world of web technologies through a series of tutorials

S7rthak

Written by

S7rthak

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Codeforces(Expert)

Weekly Webtips

Explore the world of web technologies through a series of tutorials

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store