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 given tree and sum

What is the output of the following C++ code that checks if there is a root-to-leaf path with sum 22?

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    bool result = hasPathSum(root, 22);
    std::cout << (result ? "true" : "false") << std::endl;
    return 0;
}

A Compilation error

B false

C true

D Runtime error

💡 Hint

Trace the path sums from root to leaf nodes carefully.

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

🧠 Conceptual

intermediate

Number of root-to-leaf paths with given sum

Given a binary tree and a sum, how many root-to-leaf paths have the exact sum? Consider the tree below and sum = 26. Tree structure: 5 ├─4 │ └─11 │ ├─7 │ └─2 └─8 ├─13 └─4 └─1

A 1

B 2

C 3

D 0

💡 Hint

Check all root-to-leaf paths and sum their values.

Paths 5->4->11->7 and 5->8->13 sum to 27 and 26 respectively, only one path sums to 26, so answer is 1.

🔧 Debug

advanced

Identify the error in path sum function

What error does the following code produce when checking for path sum in a binary tree?

DSA C++

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

A Syntax error due to assignment in return statement

B Logical error: always returns true

C Runtime error: null pointer dereference

D No error, works correctly

💡 Hint

Check the use of '=' vs '==' in the return statement.

The code uses '=' (assignment) instead of '==' (comparison) in the return statement, causing a syntax or logical error.

🚀 Application

advanced

Find all root-to-leaf paths with given sum

Which option correctly returns all root-to-leaf paths where the sum of node values equals the target sum?

DSA C++

void findPaths(TreeNode* root, int sum, std::vector<int>& path, std::vector<std::vector<int>>& result) {
    if (!root) return;
    path.push_back(root->val);
    if (!root->left && !root->right && root->val == sum) {
        result.push_back(path);
    } else {
        findPaths(root->left, sum - root->val, path, result);
        findPaths(root->right, sum - root->val, path, result);
    }
    path.pop_back();
}

A Fails to backtrack path, causing incorrect results

B Only finds one path even if multiple exist

C Does not check leaf nodes properly

D Correctly finds all paths with sum equal to target

💡 Hint

Check if path is popped after recursion to backtrack.

The function pushes current node, checks leaf and sum, recurses, then pops node to backtrack correctly.

❓ Predict Output

expert

Output of path sum check with negative values

What is the output of the following code snippet that checks for a path sum of 0 in a tree with negative values?

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

int main() {
    TreeNode* root = new TreeNode(-2);
    root->right = new TreeNode(-3);

    bool result = hasPathSum(root, 0);
    std::cout << (result ? "true" : "false") << std::endl;
    return 0;
}

A true

B false

C Compilation error

D Runtime error

💡 Hint

Check if any root-to-leaf path sums to zero.

The paths are -2->-3 = -5 and -2 alone is not a leaf path, so no path sums to 0.

Practice

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

easy

A. The total number of leaf nodes in the tree

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

C. The maximum depth of the binary tree

D. The sum of all node values in the 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 target sum.

2. Step 2: Differentiate from other tree properties

   It is not about depth, counting leaves, or total sum, but specifically about a path sum from root to leaf.

3. Final Answer:

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

4. Quick Check:

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

Hint: Focus on root-to-leaf paths and their sums [OK]

Common Mistakes:

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

2. Which of the following C++ function signatures correctly represents a function to check path sum in a binary tree node structure?

easy

A. bool hasPathSum(TreeNode root, int targetSum)

B. int hasPathSum(TreeNode root, int targetSum)

C. void hasPathSum(TreeNode* root, int targetSum)

D. bool hasPathSum(TreeNode* root, int targetSum)

Solution

1. Step 1: Check parameter types and return type

   The function should take a pointer to the root node (TreeNode*) and an integer target sum, and return a boolean indicating if such a path exists.

2. Step 2: Validate each option

   bool hasPathSum(TreeNode* root, int targetSum) uses pointer and bool return type, which is correct. Options B and D pass TreeNode by value (less efficient), and B returns int, C returns void which is incorrect.

3. Final Answer:

   bool hasPathSum(TreeNode* root, int targetSum) -> Option D

4. Quick Check:

   Pointer input and bool output needed [OK]

Hint: Use pointer for tree nodes and bool for yes/no answers [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using wrong return type like void or int
• Missing pointer symbol (*) in parameter

3. What will be the output of the following code snippet?

#include <iostream>

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool hasPathSum(TreeNode* root, int targetSum) {
  if (!root) return false;
  if (!root->left && !root->right) return root->val == targetSum;
  return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}

int main() {
  TreeNode* root = new TreeNode(5);
  root->left = new TreeNode(4);
  root->right = new TreeNode(8);
  root->left->left = new TreeNode(11);
  root->left->left->left = new TreeNode(7);
  root->left->left->right = new TreeNode(2);
  root->right->left = new TreeNode(13);
  root->right->right = new TreeNode(4);
  root->right->right->right = new TreeNode(1);

  bool result = hasPathSum(root, 22);
  std::cout << (result ? "true" : "false") << std::endl;
  return 0;
}

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Trace the path sums in the tree

   Check if any root-to-leaf path sums to 22. One path is 5->4->11->2 = 22.

2. Step 2: Confirm function logic and output

   The function correctly returns true if such a path exists. The code prints "true".

3. Final Answer:

   true -> Option A

4. Quick Check:

   Path 5+4+11+2 = 22 found [OK]

Hint: Check leaf paths sums carefully [OK]

Common Mistakes:

• Ignoring leaf node condition
• Subtracting values incorrectly
• Assuming no path matches without checking all

4. Identify the bug in the following code that attempts to check path sum in a binary tree:

bool hasPathSum(TreeNode* root, int targetSum) {
  if (root == nullptr) return false;
  if (root->left == nullptr && root->right == nullptr) return targetSum == root->val;
  return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}

medium

A. The leaf node check should return false instead of comparison

B. The base case incorrectly returns false for nullptr

C. The targetSum is not reduced by root->val in recursive calls

D. The function should return int instead of bool

Solution

1. Step 1: Analyze recursive calls

   The function calls itself with the same targetSum without subtracting the current node's value, so it never reduces the sum along the path.

2. Step 2: Identify correct recursive logic

   It should call hasPathSum(root->left, targetSum - root->val) and similarly for right to correctly track remaining sum.

3. Final Answer:

   The targetSum is not reduced by root->val in recursive calls -> Option C

4. Quick Check:

   Subtract node value each step [OK]

Hint: Always subtract current node value from targetSum in recursion [OK]

Common Mistakes:

• Not updating targetSum in recursive calls
• Confusing base case return values
• Returning wrong data type

5. Given a binary tree where node values can be negative, zero, or positive, which modification is necessary to correctly check for a path sum equal to a target value?

medium

A. No modification needed; the standard path sum check works for all values

B. Use a global variable to track sums instead of subtracting targetSum

C. Modify the function to return the maximum path sum instead of a boolean

D. Check all paths, not just root-to-leaf, because negative values can cancel out sums

Solution

1. Step 1: Consider negative values in path sum

   The standard recursive algorithm subtracts the current node's value (which can be negative) from the targetSum at each step, correctly handling negatives, zeros, and positives for root-to-leaf paths.

2. Step 2: No change required

   The problem is specifically for root-to-leaf paths, not arbitrary paths, so no modification is needed.

3. Final Answer:

   No modification needed; the standard path sum check works for all values -> Option A

4. Quick Check:

   Recursion handles negatives via subtraction [OK]

Hint: Standard path sum recursion works with negative node values [OK]

Common Mistakes:

• Thinking negatives require checking all paths
• Using global variables unnecessarily
• Changing return type without reason