Leetcode – Sum of Root To Leaf Binary Numbers Solution

Spread the love

The “Sum of Root To Leaf Binary Numbers” problem on Leetcode challenges your knowledge on binary trees and your skills to traverse and decode binary representations. In this comprehensive article, we will delve deep into the problem statement, the significance of the problem, potential solution approaches, and Python-based implementations.

Overview:

  1. Problem Statement
  2. Importance of the Problem
  3. Possible Approaches
  4. Python-based Solutions
  5. Testing the Solution
  6. Wrapping Up

1. Problem Statement:

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, with the most significant bit being the root.

Your task is to return the sum of these numbers. The answer is guaranteed to fit in a 32-bit integer.

Example:

Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: 
- Path 1->0->0 represents the binary number 100 which is 4.
- Path 1->0->1 represents the binary number 101 which is 5.
- Path 1->1->0 represents the binary number 110 which is 6.
- Path 1->1->1 represents the binary number 111 which is 7.
The total sum is 4 + 5 + 6 + 7 = 22.

2. Importance of the Problem:

This problem melds binary tree traversal with bitwise operations, testing not only your understanding of tree-based algorithms but also your ability to work with binary representations.

3. Possible Approaches:

  1. Recursive DFS (Depth-First Search): The natural strategy for this problem is to use a recursive approach to traverse the tree while constructing the binary numbers. The sum is calculated when a leaf node is reached.
  2. Iterative DFS: Another approach is to use an iterative DFS with a stack to traverse the tree and compute the sum.

4. Python-based Solutions:

1. Recursive DFS:

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

def sumRootToLeaf(root: TreeNode, current_num=0) -> int:
    if not root:
        return 0

    current_num = (current_num << 1) + root.val  # Left shift and add the current value

    # If it's a leaf node
    if not root.left and not root.right:
        return current_num

    return sumRootToLeaf(root.left, current_num) + sumRootToLeaf(root.right, current_num)

2. Iterative DFS:

def sumRootToLeaf(root: TreeNode) -> int:
    if not root:
        return 0

    stack = [(root, root.val)]
    total_sum = 0

    while stack:
        node, current_num = stack.pop()

        if not node.left and not node.right:
            total_sum += current_num
        if node.left:
            stack.append((node.left, (current_num << 1) + node.left.val))
        if node.right:
            stack.append((node.right, (current_num << 1) + node.right.val))

    return total_sum

5. Testing the Solution:

To ensure that our solution is correct, let’s test both methods:

# Construct the test tree: [1,0,1,0,1,0,1]
root = TreeNode(1)
root.left = TreeNode(0)
root.right = TreeNode(1)
root.left.left = TreeNode(0)
root.left.right = TreeNode(1)
root.right.left = TreeNode(0)
root.right.right = TreeNode(1)

print(sumRootToLeaf(root))  # Expected output: 22

6. Wrapping Up:

The “Sum of Root To Leaf Binary Numbers” problem is an intriguing combination of tree traversal and binary representation manipulation. By exploring both recursive and iterative solutions, we can gain a deeper understanding of depth-first traversal techniques. Python, with its expressive syntax, allows for concise and clear solutions to this problem, making it more intuitive to grasp and implement.

Leave a Reply