Sum of Left Leaves

class Solution {
  public int calculateLeftLeavesSum(TreeNode root) {
    int sum = 0;
    TreeNode current = root;
    while (current != null) {
      if (current.left == null) {
        current = current.right;
      } else {
        TreeNode temp = current.left;
        if (temp.left == null && temp.right == null) {
          sum += temp.val;
        }
        while (temp.right != null && temp.right != current) {
          temp = temp.right;
        }
        if (temp.right == null) {
          temp.right = current;
          current = current.left;
        } else {
          temp.right = null;
          current = current.right;
        }
      }
    }
    return sum;
  }
}

The provided Java program defines a method calculateLeftLeavesSum designed to calculate the sum of the left leaves in a binary tree. This method uses an iterative traversal approach to navigate through the tree, leveraging a modified version of the Morris traversal technique which avoids the need for additional memory for stack or recursion.

Here's how the method works:

1. Initialize a variable sum to zero to keep track of the cumulative sum of the leaf values.
2. Start traversing the binary tree from the root node using a current pointer.
3. Utilize a while loop to process nodes until there are no more nodes to process (current becomes null).
4. Within the loop, check if the left child of the current node does not exist:
   • If true, move to the right child of the current node.
   • Otherwise, process the left subtree of the node.
5. If the left child of the current node itself has no children, it is a left leaf:
   • Add its value to sum.
6. Check if the rightmost child of the left subtree has been visited by looking at a temporary temp that navigates through the right children.
   • If temp.right is null, it means this subtree hasn’t been fully explored:
     • Make temp.right point to the current node for a return path and then move current to its left child.
   • If temp.right is not null, it means returning after the left subtree is fully explored:
     • Set temp.right back to null to restore the original tree structure and move current to its right child.

The method continuously updates the sum whenever a left leaf is found, finally returning the sum after the tree is fully traversed. This solution is efficient as it avoids using extra space for recursion or a stack, making it suitable for large trees.

int calculateLeftLeafSum(struct TreeNode* root) {
    int total = 0;
    while (root) {
        if (!root->left) {
            root = root->right;
        } else {
            struct TreeNode* precursor = root->left;
            if (precursor->left == NULL && precursor->right == NULL) total += precursor->val;
            while (precursor->right && precursor->right != root) precursor = precursor->right;
            if (!precursor->right) {
                precursor->right = root;
                root = root->left;
            } else {
                precursor->right = NULL;
                root = root->right;
            }
        }
    }
    return total;
}

The provided C code implements a function to calculate the sum of left leaves in a binary tree. This function, calculateLeftLeafSum, uses a non-recursive approach to traverse the tree, ensuring efficient memory usage.

• The function is initialized with a total set to 0 to hold the sum of left leaf values.
• It checks each node starting from the root using a while loop.
• If the current node does not have a left child, traversal moves to the right child.
• If a left child exists, the program checks if it is a leaf (i.e., it does not have its own children). If it is a leaf, its value is added to total.
• For non-leaf left children, a "predecessor" finder loop ensures each node's left subtree is fully explored before moving back to the right subtree. This involves temporarily modifying the tree structure by making right children of discovered nodes point back to the current node. This technique avoids the use of a parent pointer or a stack.
• After a subtree is processed, the temporary pointers are reverted to restore the tree structure, and the next right child is processed.

This code effectively finds and sums the values of all left leaves in the binary tree without using additional space for recursion or a stack, which is a common challenge in similar tree problems.