Sum of Cookies Sold Each Day - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-25 mins
  • 🛠️ Topics: Trees, Breadth-First Search (BFS), Level Order 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 customer order and its value represents the number of cookies ordered.
  • What operation needs to be performed?
    • The function needs to return a list of the sums of cookies ordered at each level of the tree.
  • What should be returned?
    • The function should return a list where each element is the sum of cookies ordered at that level.
HAPPY CASE
Input: 
    order_sizes = [4, 2, 6, 1, 3]
    orders = build_tree(order_sizes)
Output: 
    [4, 8, 4]
Explanation: 
    The sum of cookies ordered on each day (level) is [4] on day 1, [2 + 6] on day 2, and [1 + 3] on day 3.

EDGE CASE
Input: 
    order_sizes = [5]
    orders = build_tree(order_sizes)
Output: 
    [5]
Explanation: 
    The tree contains only one node, so the sum is just the value of that node.

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

  • Level Order Traversal (Breadth-First Search): Since the problem requires calculating sums at each level, a BFS approach is a natural fit, as it processes nodes level by level.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform a level-order traversal of the tree using a queue. For each level, sum the values of the nodes and store the result.

1) If the tree is empty (`orders` is `None`), return an empty list.
2) Initialize an empty list `results` to store the sum of each level.
3) Initialize a queue starting with the root node.
4) While the queue is not empty:
    - Initialize `level_sum` to 0.
    - Get the number of nodes at the current level (`level_size`).
    - For each node in the current level:
        - Dequeue a node from the front of the queue.
        - Add the node's value to `level_sum`.
        - If the node has a left child, enqueue the left child.
        - If the node has a right child, enqueue the right child.
    - Append `level_sum` to `results`.
5) Return `results`.

⚠️ Common Mistakes

  • Not correctly handling the case where the tree is empty.
  • Forgetting to sum the values of all nodes at each level.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def sum_each_days_orders(orders):
    if not orders:
        return []
    
    results = []
    queue = deque([orders])  # Start with the root
    
    while queue:
        level_sum = 0
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            
            # Add child nodes to the queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Append the sum of the current level to results
        results.append(level_sum)
    
    return results
    
# Example Usage:
order_sizes = [4, 2, 6, 1, 3]
orders = build_tree(order_sizes)

print(sum_each_days_orders(orders))  # [4, 8, 4]

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: 
        `order_sizes = [4, 2, 6, 1, 3]`
        `orders = build_tree(order_sizes)`
    - Execution: 
        - Perform BFS level by level.
        - Sum of cookies ordered: [4], [2 + 6], [1 + 3].
    - Output: 
        [4, 8, 4]

- Example 2:
    - Input: 
        `order_sizes = [5]`
        `orders = build_tree(order_sizes)`
    - Execution: 
        - Only one level with one node.
        - Sum of cookies ordered: [5].
    - Output: 
        [5]

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 BFS traversal to calculate the sum at each level.

Space Complexity:

  • Space Complexity: O(N)
    • Explanation: The queue used for BFS may contain up to the entire last level of the tree, leading to a space complexity proportional to the number of nodes.