Problem
LeetCode 1022: Sum of Root To Leaf Binary Numbers (Easy)
Problem statement: Given a binary tree where each node contains a binary digit, interpret each path from the root to a leaf as a binary number, with the root value as the high-order bit. Return the sum of these numbers.
Solution
This problem is rated Easy, but it’s a good way to practice two useful techniques:
- Converting a sequence of binary digits to an integer value.
- Traversing the nodes of a binary tree in the correct sequence.
The solution described here is based on this solution by lee215, who also made an appearance last week.
Binary to decimal conversion
Consider the sequence of base-10 digits $3, 2, 1$. If we received them in that order, how would we construct the base-10 value $321$? We could use following algorithm:
result = 0
for each digit d
result *= 10
result += d
For the digit sequence above, result would take the following values: 0, 3, 30, 32, 320, and 321. For each iteration, multiplying by 10 shifts the result left, leaving a 0 value in the units place. The addition operation replaces the 0 value with the next digit in the sequence.
This algorithm works for any base. For binary, we just multiply by 2 instead of 10. So for the sequence $1, 0, 1, 0$, the result would take the values 0 (multiply), 1 (add), 2 (multiply), 2 (add), 4 (multiply), 5 (add), 10 (multiply), and 10 (add). For each iteration, we multiply by 2 (shift left) and then add either 0 or 1.
Tree traversal
Binary tree traversal comes up a lot in LeetCode problems, and an easy problem like this one is a good way to learn some fundamentals. It’s standard to use a recursive algorithm when traversing a tree, and that’s what I’ll do here. Consider a function that accepts a tree node and an the current sum, and returns a new sum. We can kick off the recursion with the root node and a sum of 0, then use the following logic for each recursive call:
if the node is null, return 0
append the current binary digit to the sum using the conversion algorithm
if the node is a leaf node, return the current sum
otherwise, return:
the value of the left subtree plus the value of the right subtree
Here’s how each line works:
if the node is null, return 0
This is the base condition. To avoid infinite recursion, we need a condition where no more recursive calls are made. If we keep following left or right pointers, we’ll eventually reach a null pointer. In this case, we don’t want to affect the sum (since we’re not on a node), so we return zero before any recursive calls happen.
append the current binary digit to the sum using the conversion algorithm
The recursive function could return an array of binary digits and the main function could convert them to decimal. But it’s cleaner to do the conversion on the fly. The binary to decimal conversion section above explains how to do that as we encounter each digit.
if the node is a leaf node, return the current sum
A leaf node is a node where both the left and right children are null. According to the problem statement, this defines the end of a binary number, so there’s nothing more to add to the sum. We can just return it.
otherwise, return:
the value of the left subtree plus the value of the right subtree
This is the “magic” step in the recursive function. Consider the situation at the root. We have already appended the root’s digit to the current sum. Now we need to incorporate the rest of the tree. But we’re at the root, so the rest of the tree is just the left and right subtrees. And each of these subtrees can have their own subtrees, and so on. The recursive design takes care of processing the left and right subtrees with minimal code. We just pass the left node and the current sum to the recursive function (call 1), pass the right node and the current sum to the recursive function (call 2), add the results together, and return the total.
Code
Sum of Root To Leaf Binary Numbers on GitHub
LeetCode Model Solutions
I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.