algoadvance

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 the binary number 01101, which is 13 in decimal.

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.

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.

Clarifying Questions:

1. What is the format for the input tree? For instance, how is the binary tree represented given the list-type input?
   • The input is provided in a level-order traversal array which can be converted to a binary tree using standard methods or helper functions.
2. Does the tree contain only binary values (i.e., 0 and 1) at each node?
   • Yes, each node’s value is constrained to be either 0 or 1.

Strategy:

1. Tree Traversal: Perform a Depth First Search (DFS) to explore all root-to-leaf paths.
2. Binary Number Construction:
   • Construct the binary number as we traverse from root to leaf.
   • Each time we move to a child node, the current binary value will be left shifted by 1 position (equivalent to multiplying by 2) and then adding the child node’s value.
3. Sum Calculation: Keep a running total of the values of all binary numbers found.

Code:

Here is a Python function to solve the problem:

# 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: TreeNode) -> int:
        def dfs(node, current):
            if not node:
                return 0
            
            current = (current << 1) | node.val
            
            # If we are at the leaf node
            if not node.left and not node.right:
                return current
            
            # Sum the values obtained from both subtrees
            return dfs(node.left, current) + dfs(node.right, current)
        
        return dfs(root, 0)

Time Complexity:

• Time Complexity: O(N), where N is the number of nodes in the binary tree. Each node is visited exactly once.
• Space Complexity:
  • The space complexity is O(H), where H is the height of the tree due to the recursion stack. In the worst case (skewed tree), the height H could be equal to N, resulting in O(N). In a balanced tree, the height H would be O(log N).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?