Path Sum Root to Leaf in Binary Tree in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the current node is a leaf node.

DSA C++

if (root->left == nullptr && root->right == [1]) {
    return sum == root->val;
}

Drag options to blanks, or click blank then click option'

A0

BNULL

Cnullptr

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or NULL instead of nullptr.

Checking only one child pointer.

A leaf node has no left or right children, so both should be nullptr.

2fill in blank

medium

Complete the code to recursively check the left subtree for the path sum.

DSA C++

if (root->left != nullptr) {
    if (hasPathSum(root->left, sum - [1])) {
        return true;
    }
}

Drag options to blanks, or click blank then click option'

Aroot->val

Bsum

Croot->left->val

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Subtracting sum instead of root->val.

Using the child's value instead of current node's value.

We subtract the current node's value from sum before checking the subtree.

3fill in blank

hard

Fix the error in the base case to handle null nodes correctly.

DSA C++

if (root == [1]) {
    return false;
}

Drag options to blanks, or click blank then click option'

Anullptr

BNULL

C0

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Using NULL or 0 instead of nullptr.

Checking root against root itself.

The base case should check if root is nullptr to avoid dereferencing null pointers.

4fill in blank

hard

Fill both blanks to recursively check left and right subtrees for the path sum.

DSA C++

return hasPathSum(root->[1], sum - root->val) || hasPathSum(root->[2], sum - root->val);

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cval

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Using val or parent instead of left or right.

Not subtracting root->val from sum.

We check both left and right children recursively for the path sum.

5fill in blank

hard

Fill all three blanks to complete the hasPathSum function.

DSA C++

bool hasPathSum(TreeNode* root, int sum) {
    if (root == [1]) return false;
    if (root->left == nullptr && root->right == nullptr) {
        return sum == root->[2];
    }
    return hasPathSum(root->[3], sum - root->val) || hasPathSum(root->right, sum - root->val);
}

Drag options to blanks, or click blank then click option'

Anullptr

Bval

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong pointer names or values.

Not handling null root correctly.

Check for null root, compare sum with root->val at leaf, and recurse left and right.

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