Sum of Root To Leaf Binary Numbers

Problem Statement

In this problem, you are provided with the root of a binary tree where each node exclusively contains a value of 0 or 1. A distinctive feature of this tree is that each path from the root to a leaf node can be understood as a representation of a binary number, with the uppermost node (root) symbolizing the most significant bit.

To elucidate, consider a path of nodes bearing the values 0 -> 1 -> 1 -> 0 -> 1. When interpreted as a binary number, this sequence translates to 01101, which is equal to the decimal value 13.

Your challenge is to compute and return the sum total of all the numbers represented by every root-to-leaf path within the given binary tree. The solution is ensured to fit within the limits of a standard 32-bit integer.

Examples

Example 1

Input:

root = [1,0,1,0,1,0,1]

Output:

22

Explanation:

(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Example 2

Input:

root = [0]

Output:

0

Constraints

• The number of nodes in the tree is in the range [1, 1000].
• Node.val is 0 or 1.

Approach and Intuition

This task entails navigating through every possible root-to-leaf path in the binary tree, converting the binary value represented by the path to a decimal number, and then summing these decimal values to produce a final result. Here's a breakdown of the method:

1. Utilize a Depth-First Search (DFS) strategy to traverse the tree. Starting from the root, move downwards through the tree exploring as far as possible along each branch before backtracking.

2. Maintain an ongoing count of the value for the current root-to-node path. This can be managed by taking the current value, shifting it left by one bit position (i.e., multiplying by 2 in binary terms), and then adding the value of the current node. This manipulation is akin to appending a bit to the end of a binary number.

3. Once a leaf node is reached (a node with no children), the accumulated value for that specific root-to-leaf path is a complete binary number. It should then be converted to its decimal equivalent (if it isn't implicitly treated as such by the programming language) and added to the total sum.

4. Ensure that every unique path is explored by recursively applying the aforementioned steps to each side of the branching node.

• Exploring different paths and correctly accumulating path values are central to the solution.
• Edge cases to consider include a tree with only the root node and the tree structure being skewed either left or right. In either scenario, ensure that the algorithms hold valid and no end node is left unvisited.

This strategy effectively captures in a binary tree each unique path's binary interpretation, ensuring that all paths contribute to the final summarized value. The boundaries set by the constraints guarantee the execution within efficient computational limits.

Solutions

class Solution {
    public int calculateSum(TreeNode node) {
        int totalSum = 0, currComposite = 0;
        int levelDepth;
        TreeNode stepBack;

        while (node != null) {
            if (node.left != null) {
                stepBack = node.left;
                levelDepth = 1;
                while (stepBack.right != null && stepBack.right != node) {
                    stepBack = stepBack.right;
                    ++levelDepth;
                }

                if (stepBack.right == null) {
                    currComposite = (currComposite << 1) | node.val;
                    stepBack.right = node;
                    node = node.left;
                } else {
                    if (stepBack.left == null) {
                        totalSum += currComposite;
                    }
                    for(int i = 0; i < levelDepth; ++i) {
                        currComposite >>= 1;
                    }
                    stepBack.right = null;
                    node = node.right;
                }
            }
            else {
                currComposite = (currComposite << 1) | node.val;
                if (node.right == null) {
                    totalSum += currComposite;
                }
                node = node.right;
            }
        }
        return totalSum;
    }
}