LeetCode 257: Binary Tree All Paths

Termination Condition Considerations

The statement if (root == nullptr) return; serves multiple critical purposes in recursive tree algorithms:

Primary Function Guard

When placed in the main function provided by LeetCode, this check handles the empty tree case. If an empty tree is passed to the main function, the algorithm terminates immediately without proceeding to the recursive helper function. This prevents unnecessary function calls and potential null pointer exceptions.

Recursive Function Termination

When a recursive function lacks a clear termination condition, this null check serves as the exit point. Consider the following flawed implementation:

void traverse(TreeNode* node, vector<int>& currentPath) {
    if (node->left == nullptr && node->right == nullptr) {
        currentPath.push_back(node->val);
        return;
    }
    traverse(node->left, currentPath);
    traverse(node->right, currentPath);
}</int>

This implementation triggers undefined behavior because when node->left is null, the code attempts to recursively process a null node. The null pointer dereference occurs when accessing node->left->left or similar properties.

Null Check Strategies

Two approaches prevent null pointer operations:

Approach 1: Early Return

void traverse(TreeNode* node, vector<int>& path) {
    if (node == nullptr) return;
    // Process node
    traverse(node->left, path);
    traverse(node->right, path);
}</int>

Approach 2: Explicit Child Checks

void traverse(TreeNode* node, vector<int>& path) {
    if (node == nullptr) return;
    path.push_back(node->val);
    if (node->left) traverse(node->left, path);
    if (node->right) traverse(node->right, path);
}</int>

Using both approaches simultaneously is redundant. The early return pattern allows recursive calls on null nodes but performs no operations, while child checks prevent null node recursion entirely.

However, omitting iether approach leads to a common LeetCode error: attempting to access child properties or values on null nodes when encountering leaf nodes or asymetric trees.

Backtracking Considerations

When implementing backtracking, explicit child checks become essential. Consider this implementation:

class Solution {
public:
    void collectPaths(TreeNode* node, vector<string>& results, vector<int>& path) {
        if (node == nullptr) return;
        
        path.push_back(node->val);
        
        if (node->left == nullptr && node->right == nullptr) {
            string formattedPath;
            for (size_t i = 0; i < path.size(); ++i) {
                formattedPath += to_string(path[i]);
                if (i < path.size() - 1) {
                    formattedPath += "->";
                }
            }
            results.push_back(formattedPath);
            return;
        }
        
        if (node->left) {
            collectPaths(node->left, results, path);
            path.pop_back();
        }
        
        if (node->right) {
            collectPaths(node->right, results, path);
            path.pop_back();
        }
    }
    
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> results;
        vector<int> path;
        
        if (root == nullptr) {
            return results;
        }
        
        collectPaths(root, results, path);
        return results;
    }
};</int></string></string></int></string>

If we replace the child checks with if (node == nullptr) return; and omit the explicit if (node->left) guards, the backtracking mechanism breaks. After processing a null child, the code would still execute path.pop_back(), incorrectly removing nodes from the path when no recursive call actually occurred.

LeetCode-Specific Pattern

Many LeetCode problems constrain you to modifying only the provided function signature. When state must persist across recursive calls (like accumulating results), you need a helper function that captures these variables as references.

The main function creates the result containers once, then passes them to the recursive helper. This approach avoids creating new containers on each recursive call, which would fragment the accumulated results across independent memory allocations.

This pattern appears consistently in problems invloving path collection, subtree traversal, and state accumulation in binary trees.