Sum of Root To Leaf Binary Numbers

You need to compute the sum of the binary numbers represented by each root-to-leaf path in a binary tree, where each node has a value of 0 or 1.

Here’s an approach to solve this problem:

1. Use Depth-First Search (DFS) to traverse the tree.
2. Maintain a current number, representing the binary number constructed from the root to the current node.
3. When reaching a leaf node, add the current number to the sum.
4. Return the total sum.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node, current_number):
            if not node:
                return 0

            # Update the current number using the value of the current node
            current_number = (current_number << 1) | node.val

            # If it's a leaf node, add the current number to the sum
            if not node.left and not node.right:
                return current_number

            # Recursively call the function on the left and right children
            return dfs(node.left, current_number) + dfs(node.right, current_number)

        # Start the DFS from the root with the current number as 0
        return dfs(root, 0)

Explanation:

• The function dfs recursively traverses the tree.
• In each call, it updates current_number by left-shifting its binary representation and adding the current node’s value (this corresponds to adding a new bit to the binary number).
• If the current node is a leaf, the function returns the current number.
• If the current node has children, the function calls itself recursively on the left and right children, and returns the sum of the results.
• Finally, the main function calls dfs starting from the root, with an initial current number of 0, and returns the result.