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

Source: Dev.to

Problem Overview

Binary trees are the backbone of hierarchical data structures, and understanding how to traverse them is a fundamental skill for any developer.
In this problem, each path from the root to a leaf represents a binary number. The task is to compute the sum of all such numbers.

Approach

The core idea is to build the binary number while traversing the tree:

• When moving down one level, shift the current value left by one position (multiply by 2) and add the node’s bit.
• Use a Depth‑First Search (DFS) to explore each branch.
• Pass the “current value” down through recursive calls.
• When a leaf node is reached, add the accumulated value to the total sum.

Key Concepts

• Pre‑order Traversal – Process the current node before its children.
• Accumulator Pattern – The current path value is carried as a parameter, avoiding global state.
• Bit Manipulation – val = (val * 2) + bit converts a sequence of bits into its decimal representation.

Example

Consider a tree where the root is 1 and the leaves form the paths (1,0,0), (1,0,1), (1,1,0), (1,1,1).

1. Start at root (1): current value = 1.
2. Move to left child (0): 1 × 2 + 0 = 2.
3. Left leaf (0): 2 × 2 + 0 = 4 → add 4.
4. Right leaf (1): 2 × 2 + 1 = 5 → add 5.
5. Repeat on the right side → values 6 and 7.

Total sum = 4 + 5 + 6 + 7 = 22.

C++ Solution

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 Solution

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  {
        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;
};

Why This Problem Matters

This “Easy” rated problem is popular in technical interviews because it simultaneously tests:

• Proficiency with tree recursion (DFS).
• Understanding of binary number construction and bit manipulation.

Similar logic appears in real‑world systems such as Huffman coding for data compression and IP routing tables (tries), where binary prefixes are stored in tree‑like structures for fast lookup. Mastering this pattern builds solid foundations for more complex system‑design challenges.