We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Root To Leaf Binary Numbers

Number: 1079

Difficulty: Easy

Paid? No

Companies: Amazon

Problem Description

Given a binary tree where each node contains a 0 or 1, every root-to-leaf path represents a binary number with the most significant bit at the root. The task is to find the sum of all these binary numbers represented by the paths from the root to each leaf.

Key Insights

  • Each root-to-leaf path can be interpreted as a binary number.
  • Use Depth-First Search (DFS) to traverse the tree.
  • Update the current accumulated binary value by shifting left (multiplying by 2) and adding the current node's value.
  • Add the computed value to the sum only when a leaf node is reached.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since each node is visited once. Space Complexity: O(h), where h is the height of the tree, due to the recursion call stack (O(n) in the worst-case for a skewed tree).

Solution

We use DFS to traverse the binary tree starting from the root. At each recursive call, the current binary value is updated by shifting the previous value left by one position and then adding the node's value. When a leaf node is reached (both children are null), the current value is added to the final sum. This method efficiently calculates the sum by leveraging bit manipulation, which mirrors how binary numbers are formed.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val      # Node's value (0 or 1)
        self.left = left    # Left child
        self.right = right  # Right child

class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        # Helper function to perform DFS traversal.
        def dfs(node, current_sum):
            if not node:
                return 0
            # Update the current sum by shifting left and adding the node's value.
            current_sum = (current_sum << 1) | node.val
            # Check if the node is a leaf.
            if not node.left and not node.right:
                return current_sum
            # Continue DFS for both children.
            return dfs(node.left, current_sum) + dfs(node.right, current_sum)
        
        return dfs(root, 0)
← Back to All Questions