Path Sum Root to Leaf in Binary Tree in DSA C

Mental Model

We want to check if there is a path from the top of the tree to any bottom leaf where the numbers add up to a target sum.

Analogy: Imagine walking down a tree from the top to the bottom, adding numbers on each branch. We want to see if any path adds up exactly to a certain number, like counting steps to reach a treasure.

    5
   / \
  4   8
 /   / \
11  13  4
/ \       \
7  2       1

Dry Run Walkthrough

Input: tree: 5->4->11->7 (leftmost path), target sum = 22

Goal: Find if any root-to-leaf path sums to 22

Step 1: start at root node 5, current sum = 22 - 5 = 17

5 [current node], target sum left: 17

Why: We subtract root value from target to track remaining sum needed

Step 2: move to left child 4, current sum = 17 - 4 = 13

5 -> 4 [current node], target sum left: 13

Why: Continue down left path subtracting node values

Step 3: move to left child 11, current sum = 13 - 11 = 2

5 -> 4 -> 11 [current node], target sum left: 2

Why: Keep subtracting to check if path sum matches target

Step 4: move to left child 7, current sum = 2 - 7 = -5

5 -> 4 -> 11 -> 7 [leaf], target sum left: -5

Why: Reached leaf but sum left is negative, path invalid

Step 5: backtrack to 11, move to right child 2, current sum = 2 - 2 = 0

5 -> 4 -> 11 -> 2 [leaf], target sum left: 0

Why: Sum left zero at leaf means path sum matches target

Result:

5 -> 4 -> 11 -> 2 -> null
Path sum 22 found: true

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Define binary tree node
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Create new node
TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Recursive function to check path sum
bool hasPathSum(TreeNode* root, int sum) {
    if (root == NULL) return false; // empty node no path

    // subtract current node value from sum
    sum -= root->val;

    // check if leaf node and sum is zero
    if (root->left == NULL && root->right == NULL) {
        return (sum == 0);
    }

    // recursively check left and right subtree
    return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);
}

int main() {
    // Build tree from dry run example
    TreeNode* root = newNode(5);
    root->left = newNode(4);
    root->right = newNode(8);
    root->left->left = newNode(11);
    root->left->left->left = newNode(7);
    root->left->left->right = newNode(2);
    root->right->left = newNode(13);
    root->right->right = newNode(4);
    root->right->right->right = newNode(1);

    int targetSum = 22;
    bool result = hasPathSum(root, targetSum);
    printf("Path sum %d found: %s\n", targetSum, result ? "true" : "false");
    return 0;
}

if (root == NULL) return false;

handle empty node base case - no path here

sum -= root->val;

subtract current node value from remaining sum

if (root->left == NULL && root->right == NULL) { return (sum == 0); }

check if leaf node and if remaining sum is zero

return hasPathSum(root->left, sum) || hasPathSum(root->right, sum);

recurse left and right subtree to find valid path

Output

Path sum 22 found: true

Complexity Analysis

Time: O(n) because we visit each node once to check paths

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative BFS, recursion is simpler but uses call stack; BFS uses queue and may use more memory

Edge Cases

empty tree

returns false because no paths exist

DSA C

if (root == NULL) return false;

single node tree where node value equals target sum

returns true because root is leaf and sum matches

DSA C

if (root->left == NULL && root->right == NULL) { return (sum == 0); }

single node tree where node value does not equal target sum

returns false because sum does not match leaf value

DSA C

if (root->left == NULL && root->right == NULL) { return (sum == 0); }

When to Use This Pattern

When asked if a root-to-leaf path sums to a target, use this pattern of subtracting node values and checking leaves to find the answer.

Common Mistakes

Mistake: Checking sum only at root or non-leaf nodes instead of at leaf nodes
Fix: Only check if sum equals zero when at a leaf node (no children)

Mistake: Not subtracting current node value from sum before recursive calls
Fix: Subtract current node value from sum before recursing to children

Summary

Checks if any root-to-leaf path in a binary tree sums to a target value.

Use when you need to verify if a path with a specific sum exists from top to bottom of a tree.

The key is to subtract node values as you go down and confirm sum zero only at leaf nodes.

Practice

1. What does the "Path Sum Root to Leaf" problem ask you to find in a binary tree?

easy

A. If there exists a root-to-leaf path with a sum equal to a given target

B. The maximum depth of the binary tree

C. The total number of leaf nodes in the binary tree

D. The sum of all node values in the binary tree

Solution

1. Step 1: Understand the problem statement

   The problem asks if there is any path from the root node down to any leaf node where the sum of the node values equals a given target sum.

2. Step 2: Differentiate from other tree properties

   This is different from finding max depth, counting leaves, or summing all nodes. It specifically checks for a path with a certain sum.

3. Final Answer:

   If there exists a root-to-leaf path with a sum equal to a given target -> Option A

4. Quick Check:

   Path sum means root-to-leaf sum check [OK]

Hint: Look for root-to-leaf path sums, not total or max values [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking any path, not root-to-leaf
• Counting nodes instead of summing values

2. Which of the following is the correct C function signature to check if a binary tree has a root-to-leaf path with a given sum?

easy

A. int hasPathSum(struct TreeNode* root, int sum);

B. void hasPathSum(struct TreeNode* root, int sum);

C. int hasPathSum(int root, int sum);

D. bool hasPathSum(struct TreeNode* root);

Solution

1. Step 1: Identify correct parameter types

   The function needs the root pointer of the tree (struct TreeNode*) and the target sum (int).

2. Step 2: Identify correct return type

   The function returns an int (usually 0 or 1) indicating false or true for path existence.

3. Final Answer:

   int hasPathSum(struct TreeNode* root, int sum); -> Option A

4. Quick Check:

   Function returns int and takes root pointer and sum [OK]

Hint: Function returns int and takes root pointer plus sum [OK]

Common Mistakes:

• Using void return type instead of int
• Passing root as int instead of pointer
• Missing sum parameter

3. Given the binary tree below and target sum = 22, what will the function hasPathSum return?

    5
   / \
  4   8
 /   / \
11  13  4
/  \      \
7    2      1

medium

A. 0

B. 1

C. Error

D. Undefined

Solution

1. Step 1: Find root-to-leaf paths and their sums

   Paths and sums: - 5->4->11->7 = 27 - 5->4->11->2 = 22 - 5->8->13 = 26 - 5->8->4->1 = 18

2. Step 2: Check if any path sum equals 22

   The path 5->4->11->2 sums to 22, so the function returns true (1).

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Path sum 22 exists = 1 [OK]

Hint: Check all root-to-leaf sums carefully [OK]

Common Mistakes:

• Ignoring leaf node condition
• Stopping at non-leaf nodes
• Miscomputing sums

4. Consider this buggy C code snippet for path sum check:

int hasPathSum(struct TreeNode* root, int sum) {
  if (!root) return 0;
  if (!root->left && !root->right && root->val == sum) return 1;
  return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

What is the bug in this code?

medium

A. It misses subtracting root->val from sum

B. It incorrectly returns 1 for non-leaf nodes

C. It does not handle empty tree correctly

D. It correctly implements the path sum check

Solution

1. Step 1: Analyze base cases

   Returns 0 if root is NULL (empty tree). Returns 1 if leaf node value equals sum.

2. Step 2: Analyze recursive calls

   Recursively checks left and right subtrees with updated sum (sum - root->val).

3. Final Answer:

   It correctly implements the path sum check -> Option D

4. Quick Check:

   Code matches standard path sum logic [OK]

Hint: Check base cases and recursive calls carefully [OK]

Common Mistakes:

• Missing leaf node check
• Not subtracting root value from sum
• Returning wrong values for NULL nodes

5. You want to modify the path sum function to return all root-to-leaf paths where the sum equals the target. Which data structure is best to store the current path during recursion?

hard

A. A queue to process nodes level by level

B. A hash map to store node values and counts

C. A stack or dynamic array to track nodes in current path

D. A linked list to store all leaf nodes

Solution

1. Step 1: Understand path tracking during recursion

   To record the current path from root to current node, a stack or dynamic array is used to push and pop nodes as recursion goes deeper or backtracks.

2. Step 2: Differentiate from other data structures

   A queue is for breadth-first traversal, hash map is for counting, linked list for storing nodes but not efficient for backtracking paths.

3. Final Answer:

   A stack or dynamic array to track nodes in current path -> Option C

4. Quick Check:

   Use stack/array for path tracking [OK]

Hint: Use stack or array to track path during recursion [OK]

Common Mistakes:

• Using queue instead of stack for path tracking
• Not backtracking path correctly
• Using hash map for path storage