The placement of code relative to a recursive call determines when it executes. Code placed before the recursive call runs during the stacking phase—when the function is first entered. Converse, code placed after the recursive call runs during the unstacking phase—after the recursive call returns.

Consider this example demonstrating pre-recursion execution:

int calculate(int num) {
    static int counter = 0;
    if (num == 1) return 1;
    if (num == 4) return counter;
    counter++;
    calculate(num - 1);
    return counter;
}

int main() {
    std::cout << calculate(5) << std::endl;
}

Output: 1

Now observe the same logic with the check moved after the recursive call:

int calculate(int num) {
    static int counter = 0;
    if (num == 1) return 1;
    counter++;
    calculate(num - 1);
    if (num == 4) return counter;
    return counter;
}

int main() {
    std::cout << calculate(5) << std::endl;
}

Output: 4

Backtracking: Concept and Purpose

Backtracking is a technique used to restore a variable's state after exploring a recursive branch. When traversing a left subtree modifies a variable, that modification persists for the right subtree unless explicitly reversed. Backtracking ensures each branch operates independently.

Approach 1: Reference Parameter with Explicit Backtracking

Using a reference parameter requires manual state restoration:

bool checkPathSum(TreeNode* node, int& remainingSum) {
    if (node == nullptr) return false;
    
    remainingSum -= node->val;
    
    if (node->left == nullptr && node->right == nullptr) {
        return remainingSum == 0;
    }
    
    if (node->left) {
        bool leftFound = checkPathSum(node->left, remainingSum);
        remainingSum += node->left->val;  // Backtrack
        if (leftFound) return true;
    }
    
    if (node->right) {
        bool rightFound = checkPathSum(node->right, remainingSum);
        remainingSum += node->right->val;  // Backtrack
        if (rightFound) return true;
    }
    
    return false;
}

Approach 2: Pass-by-Value (Implicit Backtracking)

Pasing by value automatically preserves the original state for sibling branches, eliminating the need for explicit backtracking:

bool checkPathSum(TreeNode* node, int remainingSum) {
    if (node == nullptr) return false;
    
    remainingSum -= node->val;
    
    if (node->left == nullptr && node->right == nullptr) {
        return remainingSum == 0;
    }
    
    return checkPathSum(node->left, remainingSum) || 
           checkPathSum(node->right, remainingSum);
}

While pass-by-value simplifies the code, pass-by-reference with explicit backtracking is often more memory-efficient. Each pass-by-value call creates a new copy of the parameter, which can lead to stack overflow with deep reucrsion.

Determining Termination Conditions

Identifying the correct termination condition requires understanding the problem's traversal endpoint:

• Identify the endpoint: For path sum problems, the sum accumulates until reaching a leaf node. Therefore, the base case must check for a leaf: node->left == nullptr && node->right == nullptr.
• Define success criteria: At the leaf node, verify if the accumulated sum matches the target. If the remaining sum equals zero after subtracting the leaf's value, the path is valid.