Cookie Sum

TIP102 Unit 9 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-25 mins
• 🛠️ Topics: Trees, Path Sum, Depth-First Search

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What is the structure of the tree?
  • The tree is a binary tree where each node represents a certain number of cookies.
• What operation needs to be performed?
  • The function needs to find the number of unique paths from the root to a leaf node where the sum of the nodes equals a given target_sum.
• What should be returned?
  • The function should return the number of such paths.

HAPPY CASE
Input: 
    cookie_nums = [10, 5, 8, 3, 7, 12, 4]
    cookies1 = build_tree(cookie_nums)
    target_sum = 22
Output: 
    2
Explanation: 
    There are two paths that sum to 22:
    - 10 -> 5 -> 7
    - 10 -> 8 -> 4

EDGE CASE
Input: 
    cookie_nums = [8, 4, 12, 2, 6, None, 10]
    cookies2 = build_tree(cookie_nums)
    target_sum = 14
Output: 
    1
Explanation: 
    There is only one path that sums to 14:
    - 8 -> 4 -> 2

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Path Sum problems in a tree, we want to consider the following approaches:

• Depth-First Search (DFS): DFS can be used to explore all possible paths from the root to the leaves and accumulate the sum of the node values along each path.
• Recursive Exploration: Recursively traverse the tree while keeping track of the current path sum and count how many times the sum equals the target.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

• Traverse the tree using DFS while accumulating the sum of the node values along each path. If a path sum equals the target_sum at a leaf node, increment the count of valid paths.

1) Define a helper function `dfs(node, current_sum)` that:
    - If `node` is `None`, return 0.
    - Add `node.val` to `current_sum`.
    - If `node` is a leaf and `current_sum` equals `target_sum`, return 1.
    - Recur for the left and right children of the node and return the sum of the results.
2) In the main function `count_cookie_paths(root, target_sum)`:
    - Call `dfs(root, 0)` and return the result.

⚠️ Common Mistakes

• Not correctly handling the base case where the node is None.
• Forgetting to check the sum only at leaf nodes.

4: I-mplement

Implement the code to solve the algorithm.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_cookie_paths(root, target_sum):
    if not root:
        return 0

    def dfs(node, current_sum):
        if not node:
            return 0

        current_sum += node.val
        
        # Check if we are at a leaf node and if the current path sum equals target_sum
        if not node.left and not node.right:
            return 1 if current_sum == target_sum else 0
        
        # Recur for left and right subtrees
        return dfs(node.left, current_sum) + dfs(node.right, current_sum)

    # Start DFS from the root
    return dfs(root, 0)

# Example Usage:
cookie_nums = [10, 5, 8, 3, 7, 12, 4]
cookies1 = build_tree(cookie_nums)
cookie_nums = [8, 4, 12, 2, 6, None, 10]
cookies2 = build_tree(cookie_nums)

print(count_cookie_paths(cookies1, 22))  # Output: 2
print(count_cookie_paths(cookies2, 14))  # Output: 1

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

- Example 1:
    - Input: 
        `cookie_nums = [10, 5, 8, 3, 7, 12, 4]`
        `cookies1 = build_tree(cookie_nums)`
        `target_sum = 22`
    - Execution: 
        - Traverse all root-to-leaf paths and check if their sums equal 22.
    - Output: 
        2

- Example 2:
    - Input: 
        `cookie_nums = [8, 4, 12, 2, 6, None, 10]`
        `cookies2 = build_tree(cookie_nums)`
        `target_sum = 14`
    - Execution: 
        - Traverse all root-to-leaf paths and check if their sums equal 14.
    - Output: 
        1

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

• Time Complexity: O(N) where N is the number of nodes in the tree.
  • Explanation: Each node is visited exactly once during the DFS traversal.

Space Complexity:

• Space Complexity:
  • Balanced Tree: O(log N) where N is the number of nodes, since the recursion stack depth corresponds to the tree height.
  • Unbalanced Tree: O(N) in the worst case (e.g., a skewed tree), where the tree height is equal to the number of nodes.