Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode 1022: Sum of Root To Leaf Binary Numbers

By Duncan Smith Jan 27 0

LeetCode 2021

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.

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • LeetCode 11: Container With Most Water February 24, 2021
  • LeetCode 47: Permutations II February 17, 2021
  • LeetCode 897: Increasing Order Search Tree February 10, 2021
  • LeetCode 394: Decode String February 3, 2021
  • LeetCode 1022: Sum of Root To Leaf Binary Numbers January 27, 2021
  • LeetCode 1288: Remove Covered Intervals January 20, 2021
  • LeetCode 227: Basic Calculator II January 13, 2021
  • A Project for 2021 January 6, 2021
  • Lessons from the 2020 LeetCode Monthly Challenges December 30, 2020
  • Quora: Are Math Courses Useful for Competitive Programming? December 23, 2020
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2021 Duncan Smith