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

Recall & Review

beginner

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

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

beginner

In the context of the Path Sum problem, what is a leaf node?

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

intermediate

Why do we subtract the current node's value from the target sum when moving down the tree?

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

intermediate

What is the base case for the recursive solution to 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.

intermediate

How does the recursive function decide to return true or false?

It returns true if either the left or right subtree has a path sum equal to the remaining sum after subtracting the current node's value; otherwise, it returns false.

What should the function return if the root node is NULL?

A the target sum

B true

C false

D the root node value

If the root is NULL, there is no path, so the function returns false.

When do we check if the current node's value equals the remaining sum?

A When the node has at least one child

B When the node is a leaf node

C When the node is the root

D At every node

We check this only at leaf nodes to confirm if the path sum matches the target.

What is the purpose of subtracting the current node's value from the target sum?

A To update the target sum for the next recursive call

B To reset the sum

C To find the maximum value

D To count nodes

Subtracting updates the remaining sum needed for the path.

If a node has no children and its value does not equal the remaining sum, what should the function return?

A false

B the node's value

C true

D the remaining sum

Because the path sum does not match at this leaf, return false.

Which traversal method is naturally used in the recursive solution for Path Sum?

A Inorder traversal

B Level order traversal

C Postorder traversal

D Preorder traversal

Preorder traversal is used because we process the current node before its children.

Explain how the recursive function checks for a path sum from root to leaf in a binary tree.

Think about how the function moves down the tree and updates the sum.

Describe why leaf nodes are important in the Path Sum problem and how they affect the solution.

Focus on the end condition of the path.

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