Sum of Root to Leaf Binary Numbers

Sum of Root to Leaf Binary Numbers

January 9, 2024
medium
graph, DFS

Problem #

Given a binary tree where each node can either be 0 or 1, each root-to-leaf path represents a binary number. A leaf is a node with no children. The root is the top node of the tree. Calculate the sum of these numbers.

Example: #

  1. Input:

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

    Output: 22

    Explanation: The binary numbers are 100, 101, 110, and 111, which sum to 22.

Solution Approach #

The solution involves a depth-first search (DFS) from the root to each leaf, keeping track of the current number. When a leaf is reached, add its value to the total sum.

Algorithm Steps #

  1. Define a helper function dfs that takes a node and the current value.
  2. In dfs, check if the node is a leaf. If yes, return its value.
  3. Recursively call dfs for left and right children, updating the current value by shifting it left (multiply by 2) and adding the node’s value.
  4. Start dfs from the root and accumulate the sum of all leaf values.
  5. Return the total sum.

Code (Python) # 

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

def sumRootToLeaf(root):
    def dfs(node, curr_val):
        if not node:
            return 0
        curr_val = curr_val * 2 + node.val
        if not node.left and not node.right:
            return curr_val
        return dfs(node.left, curr_val) + dfs(node.right, curr_val)
    
    return dfs(root, 0)

# Example tree construction and test
root = TreeNode(1)
root.left = TreeNode(0, TreeNode(0), TreeNode(1))
root.right = TreeNode(1, TreeNode(0), TreeNode(1))
print(sumRootToLeaf(root))  # Output: 22

Time Complexity #

The time complexity is O(n), where n is the number of nodes in the tree, as we visit each node once.

Space Complexity #

The space complexity is O(h), where h is the height of the tree, due to the recursion stack in the DFS.