Sum Root to Leaf Numbers

class Solution {
public:
    int calculateSum(TreeNode* root) {
        int total_path_sum = 0, current_path_num = 0;
        int depth;
        TreeNode* backtrace;
        while (root != NULL) {
            if (root->left != NULL) {
                backtrace = root->left;
                depth = 1;
                while (backtrace->right != NULL &&
                       backtrace->right != root) {
                    backtrace = backtrace->right;
                    ++depth;
                }
                if (backtrace->right == NULL) {
                    current_path_num = current_path_num * 10 + root->val;
                    backtrace->right = root;
                    root = root->left;
                } else {
                    if (backtrace->left == NULL) {
                        total_path_sum += current_path_num;
                    }
                    for (int i = 0; i < depth; ++i) {
                        current_path_num /= 10;
                    }
                    backtrace->right = NULL;
                    root = root->right;
                }
            } else {
                current_path_num = current_path_num * 10 + root->val;
                if (root->right == NULL) {
                    total_path_sum += current_path_num;
                }
                root = root->right;
            }
        }
        return total_path_sum;
    }
};

The provided C++ code defines a class Solution which contains the method calculateSum to calculate the sum of all numbers formed from root to leaf nodes in a binary tree. The core logic implemented uses the Morris traversal method, an efficient algorithm that traverses the tree without using additional memory for recursion or a stack.

The calculateSum function features:

• Local variables such as total_path_sum to store the cumulative sum of all path numbers, and current_path_num to store the current number as the function traverses through the tree.
• Auxiliary variables like backtrace and depth help in traversing and modifying the tree during the traversal to restore its original structure after processing each node.

The algorithm works as follows:

1. Iterate through the tree starting from the root node. Check if the current node (root) has a left child.
2. If a left child exists, find the rightmost child of this left subtree and use it to create a temporary link back to the current node (root). This helps in moving back to the current node after the left subtree is fully processed, simulating a stack-like behavior without using extra space.
3. Continue the traversal on the left subtree if the link back to the current node was just established. If returning to a node due to this temporary link, break the link and move to the right subtree.
4. If no left child is present, process the current node value into current_path_num and if it's a leaf node (no right child), add current_path_num to total_path_sum.
5. Finally, move to the right child and repeat the process.

This function modifies the tree temporarily during execution but ensures that it is restored back to its original structure using the temporary links. Upon completion, calculateSum returns the total sum of all the root-to-leaf paths in the tree.

This concise and memory-efficient algorithm enables the computation of root-to-leaf sums using Morris traversal to leverage the tree's structure without requiring additional space for traversal state management.

class Solution {
    public int calculateSum(TreeNode node) {
        int totalSum = 0, currentVal = 0;
        int depth;
        TreeNode previous;

        while (node != null) {
            // Handling the left subtree
            if (node.left != null) {
                previous = node.left;
                depth = 1;
                while (previous.right != null && previous.right != node) {
                    previous = previous.right;
                    ++depth;
                }

                // Creating a temporary bridge to backtrack later
                if (previous.right == null) {
                    currentVal = currentVal * 10 + node.val;
                    previous.right = node;
                    node = node.left;
                } else {
                    // Removal of temporary bridge and moving to right subtree
                    if (previous.left == null) {
                        totalSum += currentVal;
                    }
                    for (int i = 0; i < depth; ++i) {
                        currentVal /= 10;
                    }
                    previous.right = null;
                    node = node.right;
                }
            } else {
                // Directly moving to the right as there's no left child
                currentVal = currentVal * 10 + node.val;
                if (node.right == null) {
                    totalSum += currentVal;
                }
                node = node.right;
            }
        }
        return totalSum;
    }
}

In the provided Java solution, the code defines a method calculateSum to compute the sum of numbers represented by all root-to-leaf paths in a binary tree. Here's a concise breakdown of how the algorithm works:

• Initialize totalSum to store the cumulative sum and currentVal to track the current numerical value as each node contributes its value in the traversal.
• Use a while loop to traverse the tree. If a node has a left child, process the left subtree using Morris traversal to avoid using additional space for recursion.
• In Morris traversal:
  • Use a previous pointer to find the rightmost node of the current node's left subtree.
  • If this rightmost node's right child is not linked back to the current node (previous.right == null), create a temporary link (previous.right = node) and move to the left child of the current node.
  • If the temporary link already exists, it implies the completion of the left subtree's traversal. At this point, check if the node is a leaf node to add currentVal to totalSum before breaking the temporary link and moving to the right child.
• If a node does not have a left child, append its value to currentVal and check if it's a leaf node (when there's also no right child) to update totalSum.
• Continue this until all nodes are processed.

This solution efficiently traverses the tree using a non-recursive approach, ensuring that each leaf-to-root path computes a number that gets summed to totalSum. The use of Morris traversal ensures that the space complexity remains constant, i.e., O(1), making it a space-optimized solution for the given problem.

int calculateSum(struct TreeNode* node) {
    int total_sum = 0, current_sum = 0;
    int count_steps;
    struct TreeNode* link_node;
    while (node != NULL) {
        if (node->left != NULL) {
            link_node = node->left;
            count_steps = 1;
            while (link_node->right != NULL && link_node->right != node) {
                link_node = link_node->right;
                ++count_steps;
            }
            if (link_node->right == NULL) {
                current_sum = current_sum * 10 + node->val;
                link_node->right = node;
                node = node->left;
            } else {
                if (link_node->left == NULL) {
                    total_sum += current_sum;
                }
                for (int i = 0; i < count_steps; ++i) {
                    current_sum /= 10;
                }
                link_node->right = NULL;
                node = node->right;
            }
        } else {
            current_sum = current_sum * 10 + node->val;
            if (node->right == NULL) {
                total_sum += current_sum;
            }
            node = node->right;
        }
    }
    return total_sum;
}

In this C programming solution for summing root-to-leaf numbers in a binary tree, a special traversal method, known as Morris traversal, is used to efficiently calculate the sum without needing extra space for recursion stack or memory overhead due to use of iteration.

The function calculateSum takes a pointer to the root of a binary tree and calculates the total sum of all numbers formed by root-to-leaf paths. Here's a breakdown:

• total_sum: Stores the cumulative sum of all root-to-leaf numeric values.
• current_sum: Keeps the current numerical value being formed as the traversal progresses from root to leaf.
• count_steps: A counter to manage the depth of the current path (number of nodes).
• link_node: A pointer used to facilitate the tree modifications and restore structure during traversal.

The Morris traversal methodology involves manipulating the tree's structure by temporarily setting the right pointers of nodes:

• Traverse the tree starting from the root.
• For each node, if it has a left child, explore as far left as possible and setup temporary links back to the parent node for easy backtracking.
• If a node has no left child, add its value to current_sum.
• Multiply current_sum by 10 each time a node is successfully visited to shift the number to the left, thereby appending the next digit from the binary tree.
• If reaching a leaf node (node with no children), add current_sum to total_sum.
• Use previously made temporary links to backtrack.
• Reduce current_sum appropriately as you backtrack, ensuring it represents the correct number when exiting from leaf to root.

The traversal ensures all nodes are visited once, modifying tree structure temporarily with minimal space, and efficiently calculates the total sum by accumulating values upon reaching leaf nodes.

Ultimately, the function returns the accumulated total_sum after traversing all root-to-leaf paths. This approach significantly reduces space complexity typically required for recursive tree traversals, dealing with large structures more effectively.

function calculateSum(rootNode, accumulatedSum = 0) {
    if (!rootNode) {
        return 0;
    }
    accumulatedSum = accumulatedSum * 10 + rootNode.val;
    if (!rootNode.left && !rootNode.right) {
        return accumulatedSum;
    }
    return (
        calculateSum(rootNode.left, accumulatedSum) + calculateSum(rootNode.right, accumulatedSum)
    );
}

This solution handles the problem of summing up all the numbers formed by the paths from the root to the leaf nodes of a binary tree, where each path forms a number by concatenating the node values as digits.

The function calculateSum is implemented in JavaScript and operates using recursion. It accepts two parameters: rootNode, which is the current node in the tree, and accumulatedSum, which keeps track of the number formed along the current path. Here's how the function works:

• When rootNode is null, indicating you've reached beyond a leaf node, the function returns 0.
• The function multiplies the accumulatedSum by 10 and adds the value of rootNode.val to shift the digit left and append the current node's value.
• If the current node is a leaf (i.e., it doesn't have left or right children), the function returns accumulatedSum, which at this point represents a complete number from root to this leaf.
• If the current node is not a leaf, the function recursively calls itself for the left and right children of the current node, summing up the results to get the aggregate sum from all leaf-formed numbers.

This method ensures that all values from root to leaf paths are appropriately converted into numerical forms and summed, providing a single result that represents the sum of all path-based numbers in the given binary tree. The initial call to this function should pass the root of the tree and 0 as arguments to start the process.

class Solution:
    def calculateSum(self, rootNode: TreeNode) -> int:
        totalSum = currentNodeValue = 0

        while rootNode:
            if rootNode.left:
                predecessor = rootNode.left
                moveSteps = 1
                while predecessor.right and predecessor.right is not rootNode:
                    predecessor = predecessor.right
                    moveSteps += 1

                if predecessor.right is None:
                    currentNodeValue = currentNodeValue * 10 + rootNode.val
                    predecessor.right = rootNode
                    rootNode = rootNode.left
                else:
                    if predecessor.left is None:
                        totalSum += currentNodeValue
                    for _ in range(moveSteps):
                        currentNodeValue //= 10
                    predecessor.right = None
                    rootNode = rootNode.right
            else:
                currentNodeValue = currentNodeValue * 10 + rootNode.val
                if rootNode.right is None:
                    totalSum += currentNodeValue
                rootNode = rootNode.right

        return totalSum

The provided Python solution focuses on determining the sum of all numbers formed by root-to-leaf paths in a binary tree. The problem is addressed using a non-recursive method with a space optimization technique known as Morris traversal. Below are the core components and steps involved:

• The function starts by initializing totalSum and currentNodeValue to zero, which will store the overall sum of numbers and the current number value from root to the current node, respectively.

• The function uses a while loop to traverse through each node of the tree until all nodes are visited (rootNode is not null). Inside the loop:

  • For nodes with a left child, the algorithm finds the inorder predecessor of the current node.

  • It counts the steps needed to reach this predecessor (using moveSteps).

  • If the predecessor node’s right child is null (indicating the first visit to this node), it appends the current node value to currentNodeValue, makes the current node (rootNode) a temporary right child of its predecessor, and then moves on to this node's left child.

  • If the predecessor’s right child points to the current node (indicating a revisit), the algorithm potentially adds to totalSum if it’s a leaf node. It also cleans up the temporary pointers and updates currentNodeValue by removing digits corresponding to the number of moves taken, finally moving to the right child of the current node.

  • For nodes without a left child, the algorithm directly appends the current node's value to currentNodeValue. If it’s a leaf node (no right child), it adds to the total sum. It then moves on to the right child.

• At the end, totalSum is returned which holds the sum of all the numbers obtained from root to each leaf.

This approach effectively reduces the space complexity by avoiding the use of additional data structures for recursion or stack, instead manipulating tree structure temporarily and restoring it back during the traversal. This ensures an efficient and optimized solution for finding the sum of root-to-leaf numbers in a binary tree.