Path Sum Root to Leaf in Binary Tree in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does "Path Sum Root to Leaf" mean in a binary tree?

It means finding if there is a path from the root node down to any leaf node where the sum of all node values equals a given number.

beginner

What is a leaf node in a binary tree?

A leaf node is a node that has no children, meaning both its left and right pointers are null.

intermediate

In the path sum problem, why do we subtract the current node's value from the target sum as we go down the tree?

Because we want to check if the remaining sum can be found in the subtree. Subtracting the current node's value updates the target for the next nodes.

intermediate

What is the base case when using recursion to solve the path sum problem?

When the current node is null, return false because no path exists. When the current node is a leaf, check if its value equals the remaining sum.

beginner

How do you know if a path sum exists in the binary tree?

If any path from root to leaf has node values adding up exactly to the target sum, return true; otherwise, false.

What should you check first when solving the path sum problem recursively?

A If the tree is balanced

B If the current node has two children

C If the current node is null

D If the sum is zero

The first check is if the current node is null, which means no path exists here.

When do you return true in the path sum problem?

A When the current node is a leaf and its value equals the remaining sum

B When the current node has at least one child

C When the sum is greater than zero

D When the root is null

You return true only if you reach a leaf node and the remaining sum equals that leaf's value.

What is the main technique used to solve the path sum problem?

A Recursion

B Sorting

C Dynamic programming

D Hashing

Recursion is used to explore all paths from root to leaves.

If the target sum is 22 and the root node value is 5, what is the new sum to check in the children?

A 5

B 27

C 22

D 17

Subtract the root value 5 from 22, so the new sum to check is 17.

Which nodes do you consider when checking for path sum?

A Only root nodes

B All nodes from root to leaf

C Only leaf nodes

D Only nodes with two children

You consider all nodes along the path from root to leaf.

Explain how recursion helps to find if a path sum exists from root to leaf in a binary tree.

Think about how you reduce the problem size at each step.

Describe the steps to check if a binary tree has a root-to-leaf path with a given sum.

Imagine walking down the tree and keeping track of the remaining sum.

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