Sum of Root To Leaf Binary Numbers in Python

Navigate to Other Solutions

Code Solution


class Solution:
  def sumRootToLeaf(self, root: TreeNode | None) -> int:
    ans = 0

    def dfs(root: TreeNode | None, val: int) -> None:
      nonlocal ans
      if not root:
        return
      val = val * 2 + root.val
      if not root.left and not root.right:
        ans += val
      dfs(root.left, val)
      dfs(root.right, val)

    dfs(root, 0)
    return ans

Problem Description

Welcome to the whimsical world of binary trees, where every leaf is a potential goldmine of binary numbers! The problem at hand, “Sum of Root To Leaf Binary Numbers,” is like trying to find the total amount of candy you can collect from a tree of sweets. Imagine each path from the root to a leaf as a treasure map, where each node adds a bit of sweetness (or binary value) to your haul.

In simpler terms, you need to traverse a binary tree and calculate the sum of all the binary numbers formed from the root to each leaf. So, if you think of each path as a binary number, your task is to add them all up. It’s like counting how many times you can say “I love chocolate” while trying to eat a chocolate fountain—endless and delicious!

Approach Explanation

The provided code uses a depth-first search (DFS) approach to traverse the binary tree. Starting from the root, it builds the binary number by shifting the current value left (multiplying by 2) and adding the current node’s value. When it reaches a leaf node, it adds the constructed binary number to the total sum. This process continues recursively for both left and right children until all paths are explored.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the number of nodes in the tree. Each node is visited exactly once.
Space Complexity	O(H), where H is the height of the tree. This accounts for the space used by the recursion stack.

Real-World Example

Imagine you are a treasure hunter, and each path in a forest represents a different route to hidden treasure. Each tree branch you encounter has a sign that indicates how much treasure (binary value) you can collect. Your goal is to find out how much treasure you can gather by exploring all possible paths from the starting point (the root) to the end of each path (the leaves). The sum of all treasures collected from each path is your ultimate prize!