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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Root To Leaf Binary Numbers

Difficulty: Easy

Problem Description

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 all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

Key Insights

  • Each root-to-leaf path can be interpreted as a binary number.
  • The value of each binary number can be calculated using bit manipulation or by traversing the tree.
  • Depth-first search (DFS) or breadth-first search (BFS) can be used to traverse the tree and compute the sum of binary values.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, as we need to visit each node once.
Space Complexity: O(H), where H is the height of the tree, due to the recursive call stack in DFS.

Solution

To solve the problem, we can use a Depth-First Search (DFS) approach. Starting from the root, we traverse the tree down to each leaf node. At each node, we maintain a running total that represents the binary number formed by the path from the root to that node. When we reach a leaf node, we add the total to our final sum. This can be done using a recursive function that passes the current total along with the recursive calls.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sumNumbers(root: TreeNode) -> int:
    def dfs(node, current_sum):
        if not node:
            return 0
        current_sum = (current_sum << 1) | node.val  # Shift left and add current node's value
        if not node.left and not node.right:  # Check if it's a leaf node
            return current_sum
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)  # Recur for left and right children

    return dfs(root, 0)
← Back to All Questions