Most Popular Cookie Combo - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 25-30 mins
🛠️ Topics: Trees, Subtree Sum, Postorder Traversal

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 of a particular type.
What operation needs to be performed?
- The function needs to find the most frequent subtree sum (cookie combo) in the tree.
What should be returned?
- The function should return an array of the most frequent subtree sums. If there is a tie, return all the most frequent sums in any order.

HAPPY CASE
Input: 
    cookies1 = TreeNode(5, TreeNode(2), TreeNode(-3))
Output: 
    [2, 4, -3]
Explanation: 
    The subtree sums are:
    - Subtree rooted at node with value 2: sum = 2
    - Subtree rooted at node with value -3: sum = -3
    - Subtree rooted at node with value 5: sum = 4
    All sums appear once, so they are all returned.

EDGE CASE
Input: 
    cookies2 = TreeNode(5, TreeNode(2), TreeNode(-5))
Output: 
    [2]
Explanation: 
    The subtree sums are:
    - Subtree rooted at node with value 2: sum = 2
    - Subtree rooted at node with value -5: sum = -5
    - Subtree rooted at node with value 5: sum = 2
    The sum 2 appears twice, which is more frequent than any other sum.

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 Subtree Sum problems, we want to consider the following approaches:

Postorder Traversal: Postorder traversal is ideal here as it allows us to calculate the sum of each subtree before handling the parent node.
Hash Maps: Use a hash map to store the frequency of each subtree sum.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

Perform a postorder traversal of the tree to calculate the sum of each subtree. Use a hash map to track the frequency of each sum. Finally, identify the sum(s) that appear most frequently.

1) Define a helper function `postorder(node)` that:
    - If `node` is `None`, return 0.
    - Compute the sum of the left subtree.
    - Compute the sum of the right subtree.
    - Calculate the total sum of the current subtree as `node.val + left_sum + right_sum`.
    - Record the frequency of this sum in a hash map.
    - Return the total sum of the subtree.

2) In the main function `most_popular_cookie_combo(root)`:
    - Initialize a hash map `sum_count` to store the frequency of each subtree sum.
    - Call `postorder(root)` to populate the hash map.
    - Identify the maximum frequency from the hash map.
    - Collect and return all sums that have this maximum frequency.

⚠️ Common Mistakes

Forgetting to account for the frequency of each subtree sum when identifying the most popular cookie combo.
Not correctly handling the case where the tree is empty.

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 most_popular_cookie_combo(root):
    if not root:
        return []
    
    def postorder(node):
        if not node:
            return 0
        # Compute the sum of the left and right subtrees and the current node's value
        left_sum = postorder(node.left)
        right_sum = postorder(node.right)
        total_sum = node.val + left_sum + right_sum
        
        # Record the frequency of the current subtree sum
        if total_sum in sum_count:
            sum_count[total_sum] += 1
        else:
            sum_count[total_sum] = 1
        
        return total_sum
    
    sum_count = {}
    postorder(root)
    
    # Find the maximum frequency
    max_freq = max(sum_count.values())
    
    # Collect all sums with the maximum frequency
    result = [s for s, count in sum_count.items() if count == max_freq]
    
    return result

# Example Usage:
cookies1 = TreeNode(5, TreeNode(2), TreeNode(-3))
cookies2 = TreeNode(5, TreeNode(2), TreeNode(-5))

print(most_popular_cookie_combo(cookies1))  # Output: [2, 4, -3]
print(most_popular_cookie_combo(cookies2))  # Output: [2]

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: 
        `cookies1 = TreeNode(5, TreeNode(2), TreeNode(-3))`
    - Execution: 
        - Traverse the tree using postorder traversal and calculate subtree sums.
        - Record the frequency of each sum.
    - Output: 
        [2, 4, -3]

- Example 2:
    - Input: 
        `cookies2 = TreeNode(5, TreeNode(2), TreeNode(-5))`
    - Execution: 
        - Traverse the tree using postorder traversal and calculate subtree sums.
        - Identify that the sum 2 appears most frequently.
    - Output: 
        [2]

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: We visit each node exactly once during the postorder traversal and perform constant-time operations within each visit.

Space Complexity:

Space Complexity:
- Balanced Tree: O(N) where N is the number of nodes in the tree.
  - Explanation: The hash map stores the frequency of each subtree sum, and in the worst case, there could be N unique sums.
- Unbalanced Tree: O(N) where N is the number of nodes in the tree.
  - Explanation: The recursion stack may go as deep as the height of the tree, which could be N in the worst case (e.g., a skewed tree).