Sum Of Root To Leaf Binary Numbers - Leetcode Solution

The problem "Sum Of Root To Leaf Binary Numbers" on LeetCode asks us to find the sum of all root-to-leaf binary numbers in a given binary tree.

Let's start with understanding the problem statement:

We have a binary tree, where a value of either 0 or 1 is assigned to each node.

The root-to-leaf binary number is the binary representation of the value obtained by concatenating the values of all nodes on the path from the root to that leaf.

We need to find the sum of all these binary numbers for all the possible leaf nodes.

For example, let's consider the following binary tree:

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

Here, there are four leaf nodes - 0->0, 0->1, 1->0, and 1->1. The root-to-leaf binary numbers for each of these nodes are:

• 0->0: 100
• 0->1: 101
• 1->0: 110
• 1->1: 111

The sum of all these binary numbers is 100 + 101 + 110 + 111 = 522.

Now, let's move on to the solution for this problem:

We can solve this problem by using a recursive approach, where we traverse the binary tree from the root to each leaf node and calculate the binary number representation for each leaf node. We can then calculate the sum of all these binary numbers and return the sum as the final output.

The recursive function will take the current node, the current binary number, and the total sum as the input parameters. We will start the traversal from the root node with a binary number of 0 and a total sum of 0.

The base case for the recursion will be when we reach a leaf node. At this point, we can calculate the binary number representation and add it to the total sum.

For each non-leaf node, we will pass the left and right child nodes to the recursive function. We will also calculate the binary number representation for each child node by left-shifting the current binary number by 1 and adding the value of the child node.

We will then return the total sum calculated from the left and right child nodes.

The complete solution in Python can be written as follows:

class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        def dfs(node, cur):
            if not node:
                return 0
            cur = (cur << 1) + node.val
            if node.left == node.right:
                return cur
            return dfs(node.left, cur) + dfs(node.right, cur)
        
        return dfs(root, 0)

Here, we have defined a helper function dfs that performs the recursive traversal and binary number calculation. The function takes two parameters - the current node and the current binary number.

In the function, we check if the current node exists or not. If it doesn't exist, we return 0. Otherwise, we calculate the binary number by left-shifting the current binary number by 1 and adding the value of the current node.

If the current node is a leaf node (i.e., it doesn't have any child nodes), we return the current binary number as the result.

If the current node is not a leaf node, we recursively call the dfs function on the left and right child nodes. We add the result of these recursive calls and return it as the final output.

Finally, we call the dfs function with the root node and an initial binary number of 0, and return the result.

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we traverse each node exactly once.

The space complexity of this solution is also O(n), as the maximum number of recursive calls in the call stack is equal to the height of the binary tree, which can be at most n in the worst case.

1