LeetCode: 1022. Sum of Root To Leaf Binary Numbers

The Problem

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.

• For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

The test cases are generated so that the answer fits in a 32-bits integer.

Example

Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Node.val is 0 or 1.

Solution

We opted for a recursive approach to tackle this problem, and upon evaluating our solution on the LeetCode platform, we achieved the following outcome:

Here's the code that led us to this result.

int sumRootToLeaf(TreeNode* root) {
    int ans = 0;
    sumRootToLeaf(root, ans, 0);
    return ans;
}

void sumRootToLeaf(TreeNode* root, int &sum, int prev) {

    if (root == nullptr) return;
    int current = (prev << 1) + root->val;

    if(root->left == nullptr && root->right == nullptr)
	    sum += current;
    else {
        sumRootToLeaf(root->left, sum, current);
        sumRootToLeaf(root->right, sum, current);
    }
}

Let's break down the code step by step:

The sumRootToLeaf function is defined to calculate the sum of binary numbers along root-to-leaf paths in a binary tree. It takes three parameters:

• TreeNode* root: A pointer to the current node being processed.
• int &sum: A reference to the sum that will be updated throughout the traversal.
• int prev: The binary number represented by the path from the root to the current node's parent.

Inside the sumRootToLeaf function:

• The base case is checked: if root is nullptr, the function returns immediately.
• The binary value for the current node is calculated using bitwise operations. It takes the previous value (prev), shifts it to the left by one position (effectively multiplying by 2), and adds the value of the current node (root->val). This step represents appending the current node's value to the binary number represented by the path from the root to the parent node.

1. An if condition checks if the current node is a leaf node (both left and right children are nullptr). If it is a leaf, the value represented by the current path (current) is added to the sum. This is because the current path forms a complete binary number from root to leaf, and the goal is to accumulate the sum of these numbers.

If the current node is not a leaf, the else block is executed:

• The function is recursively called for the left child, passing in the updated sum, the current value, and the left child as the new root.
• The function is also recursively called for the right child in a similar manner.

Finally, the main function int sumRootToLeaf(TreeNode* root) initializes the process:

• It declares an integer ans to store the final sum.
• It calls the sumRootToLeaf function with the root node, the ans variable, and an initial value of 0 (since there is no previous value when starting from the root).
• After the traversal, it returns the calculated sum.