Code Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node, curr):
            if not node:
                return 0
            curr = (curr << 1) | node.val
            if not node.left and not node.right:
                return curr
            return dfs(node.left, curr) + dfs(node.right, curr)
        return dfs(root, 0)
      

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        return dfs(root, 0);
    }
private:
    int dfs(TreeNode* node, int curr) {
        if (!node) return 0;
        curr = (curr << 1) | node->val;
        if (!node->left && !node->right) return curr;
        return dfs(node->left, curr) + dfs(node->right, curr);
    }
};
      

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode() {}
//     TreeNode(int val) { this.val = val; }
//     TreeNode(int val, TreeNode left, TreeNode right) {
//         this.val = val;
//         this.left = left;
//         this.right = right;
//     }
// }

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }
    private int dfs(TreeNode node, int curr) {
        if (node == null) return 0;
        curr = (curr << 1) | node.val;
        if (node.left == null && node.right == null) return curr;
        return dfs(node.left, curr) + dfs(node.right, curr);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumRootToLeaf = function(root) {
    function dfs(node, curr) {
        if (!node) return 0;
        curr = (curr << 1) | node.val;
        if (!node.left && !node.right) return curr;
        return dfs(node.left, curr) + dfs(node.right, curr);
    }
    return dfs(root, 0);
};
      

Problem Description

Given the root of a binary tree where each node contains a value of 0 or 1, each root-to-leaf path can be interpreted as a binary number. The task is to compute the sum of all root-to-leaf binary numbers represented by the tree.

• Each path from the root to a leaf forms a binary number, with the root as the most significant bit.
• A leaf is a node with no children.
• Return the sum of these numbers as an integer.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Each node's value is either 0 or 1.

Thought Process

To solve this problem, we need to traverse all paths from the root to every leaf node in the binary tree. For each path, we interpret the sequence of node values as a binary number. The main challenge is to efficiently accumulate the binary value as we traverse and sum all such numbers.

A brute-force approach would involve:

• Finding all paths from root to leaf.
• Converting each path (a list of 0s and 1s) to a binary integer.
• Summing these integers.

Solution Approach

We use a depth-first search (DFS) traversal to visit every root-to-leaf path. At each node, we maintain the current binary number formed by the path from the root to the current node.

• At each step, we shift the current value left by one (equivalent to multiplying by 2) and add the current node's value using bitwise OR.
• When a leaf node is reached, we return the current value, as it represents a complete root-to-leaf binary number.
• The recursive calls sum up the values from all root-to-leaf paths.

This approach is efficient because:

• It does not require storing all paths explicitly.
• It uses bit manipulation for fast computation of binary numbers.
• It visits each node exactly once.

Example Walkthrough

Consider the following binary tree:

        1
       / \
      0   1
     / \ / \
    0  1 0  1
  

The root-to-leaf paths are:

• 1 → 0 → 0 (binary 100) = 4
• 1 → 0 → 1 (binary 101) = 5
• 1 → 1 → 0 (binary 110) = 6
• 1 → 1 → 1 (binary 111) = 7

Step-by-step, as we traverse:

• Start at root (1): current = 1
• Go left to 0: current = (1 << 1) | 0 = 2
• Go left to 0: current = (2 << 1) | 0 = 4 (leaf, add 4)
• Backtrack to 0, go right to 1: current = (2 << 1) | 1 = 5 (leaf, add 5)
• Back to root, go right to 1: current = (1 << 1) | 1 = 3
• Go left to 0: current = (3 << 1) | 0 = 6 (leaf, add 6)
• Go right to 1: current = (3 << 1) | 1 = 7 (leaf, add 7)

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(N*H), where N is the number of nodes and H is the height of the tree (since each path can be of length H and we might store all paths).
• Space Complexity: O(H) for recursion stack plus O(N*H) for storing all paths.

• Time Complexity: O(N), since each node is visited exactly once.
• Space Complexity: O(H), where H is the height of the tree (recursion stack).

Summary

The "Sum of Root To Leaf Binary Numbers" problem is elegantly solved using a recursive DFS traversal. By accumulating the binary number as we traverse and using bit manipulation, we avoid unnecessary storage and redundant computation. This approach is both intuitive and efficient, leveraging the structure of the tree and properties of binary numbers for a clean solution.