🌳 Beginner-Friendly Guide ‘Sum of Root To Leaf Binary Numbers’ – Problem 1022 (C++, Python, JavaScript)

Posted on by — No Comments ↓

Binary trees are the backbone of hierarchical data structures, and understanding how to traverse them is a fundamental skill for any developer. This problem challenges you to view a path from the root to a leaf as a sequence of bits, turning a tree traversal into a mathematical calculation. It is a perfect way to practice Depth First Search (DFS) while brushing up on your binary-to-decimal conversions.

Problem Summary

You’re given:
A binary tree where every node contains either a 0 or a 1. Each path starting from the root and ending at a leaf node represents a binary number.

Your goal:
Calculate the decimal value of every root-to-leaf path and return the total sum of all these values.

Intuition

The core logic revolves around how binary numbers are built. When you move down one level in the tree, you are essentially shifting the current binary value to the left by one position and adding the new bit. In decimal terms, “shifting left” is the same as multiplying the current value by 2.

We use a Depth First Search (DFS) approach to explore each branch. As we go deeper, we pass the “current value” down to the child nodes. Once we hit a leaf node (a node with no children), we know we have completed a full binary number, and we add that completed value to our total sum.

Walkthrough: Understanding the Examples

Let’s look at Example 1, where the tree structure represents paths like (1, 0, 0) and (1, 1, 1).

  1. Start at Root (1): Our current value is 1.
  2. Move to Left Child (0): We update our value: $1 times 2 + 0 = 2$.
  3. Move to Left Leaf (0): We update again: $2 times 2 + 0 = 4$. Since this is a leaf, we add 4 to our sum.
  4. Move to Right Leaf (1): From the middle step (where value was 2), we go right: $2 times 2 + 1 = 5$. We add 5 to our sum.

Repeating this for the right side of the tree gives us values 6 and 7. The final result is $4 + 5 + 6 + 7 = 22$.

Code Blocks

C++

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int totalSum = 0;
        dfs(root, 0, totalSum);
        return totalSum;
    }

private:
    void dfs(TreeNode* node, int currentVal, int& totalSum) {
        if (node == nullptr) return;

        // Shift left (multiply by 2) and add the current node's bit
        currentVal = currentVal * 2 + node->val;

        // If it's a leaf node, add the accumulated value to the total
        if (node->left == nullptr && node->right == nullptr) {
            totalSum += currentVal;
            return;
        }

        dfs(node->left, currentVal, totalSum);
        dfs(node->right, currentVal, totalSum);
    }
};

Python

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        self.total_sum = 0

        def dfs(node, current_val):
            if not node:
                return

            # Binary shift logic: current_val * 2 is equivalent to current_val << 1
            current_val = (current_val * 2) + node.val

            # Check if we reached a leaf node
            if not node.left and not node.right:
                self.total_sum += current_val
                return

            dfs(node.left, current_val)
            dfs(node.right, current_val)

        dfs(root, 0)
        return self.total_sum

JavaScript

var sumRootToLeaf = function(root) {
    let totalSum = 0;

    const dfs = (node, currentVal) => {
        if (!node) return;

        // Build the number as we descend
        currentVal = (currentVal * 2) + node.val;

        // If both children are null, we are at a leaf
        if (!node.left && !node.right) {
            totalSum += currentVal;
            return;
        }

        dfs(node.left, currentVal);
        dfs(node.right, currentVal);
    };

    dfs(root, 0);
    return totalSum;
};

Key Takeaways

  • Pre-order Traversal: This problem is a classic application of DFS where we process the current node before moving to its children.
  • Accumulator Pattern: Passing a value down through recursive calls allows us to maintain “state” (the current path value) without using global variables or complex tracking.
  • Bit Manipulation Logic: Understanding that $val = (val times 2) + bit$ is the standard way to convert a sequence of bits into a decimal integer.

Final Thoughts

This problem is a favorite for technical interviews because it tests two things at once: your comfort with tree recursion and your understanding of basic binary math. In the real world, similar logic is used in Huffman Coding for data compression and in IP routing tables, where prefixes are stored in tree-like structures (Tries) to quickly determine where data packets should be sent. Mastering these “Easy” rated problems builds the muscle memory you need for complex system design.

Leave a Reply