Path Sum Root to Leaf in Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Path Sum Check for Simple Tree

What is the output of the following C code that checks if there is a root-to-leaf path with the given sum in a binary tree?

DSA C

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

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

int main() {
    struct TreeNode n3 = {3, NULL, NULL};
    struct TreeNode n4 = {4, NULL, NULL};
    struct TreeNode n5 = {5, NULL, NULL};
    struct TreeNode n2 = {2, &n4, &n5};
    struct TreeNode root = {1, &n3, &n2};

    int result = hasPathSum(&root, 8);
    printf("%d\n", result);
    return 0;
}

A 1

B 0

C Compilation error

D Runtime error

💡 Hint

Trace the path sums from root to each leaf node and check if any equals 8.

The paths are 1->3 (sum 4), 1->2->4 (sum 7), and 1->2->5 (sum 8). Since 1->2->5 sums to 8, the function returns 1 (true).

🧠 Conceptual

intermediate

Number of Paths with Given Sum in Binary Tree

If a binary tree has 3 root-to-leaf paths with sums 7, 8, and 10 respectively, how many paths will the function hasPathSum(root, 8) return true for?

A 0

B 2

C 3

D 1

💡 Hint

The function returns true if at least one path matches the sum.

Only one path has sum 8, so the function returns true (1).

🔧 Debug

advanced

Identify the Bug in Path Sum Function

What error will this code produce when checking path sum in a binary tree?

DSA C

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

A Compilation error due to missing return

B Returns 1 if any path matches sum

C Always returns 0 for non-leaf nodes with one child

D Runtime error due to null pointer dereference

💡 Hint

Check the logical operator used to combine recursive calls.

Using && requires both left and right subtrees to have matching paths, which fails if one child is NULL.

❓ Predict Output

advanced

Output of Path Sum Check with Negative Values

What is the output of this code checking path sum in a tree with negative values?

DSA C

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

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

int main() {
    struct TreeNode n1 = {1, NULL, NULL};
    struct TreeNode n_2 = {-2, NULL, NULL};
    struct TreeNode n_3 = {-3, NULL, NULL};
    struct TreeNode n11 = {11, NULL, NULL};
    struct TreeNode n_5 = {-5, &n11, NULL};
    struct TreeNode root = {10, &n_2, &n_3};
    n_2.left = &n1;
    n_2.right = &n_5;

    int result = hasPathSum(&root, 18);
    printf("%d\n", result);
    return 0;
}

A 1

B 0

C Runtime error

D Compilation error

💡 Hint

Check all root-to-leaf paths and their sums carefully.

The paths and sums are: 10->-2->1=9, 10->-2->-5->11=14, 10->-3=7. None equals 18, so output is 0.

🚀 Application

expert

Count All Root-to-Leaf Paths with Given Sum

Given a binary tree, which code snippet correctly counts the number of root-to-leaf paths that sum to a target value?

A

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

B

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

C

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

D

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

💡 Hint

Count paths by adding counts from left and right subtrees; return 1 only if leaf matches sum.

Option A correctly returns 1 for matching leaf paths and sums counts from subtrees. Others use wrong return values or operators.

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