Sweetness Difference - 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 chocolate, and the value represents the sweetness level of that chocolate.
  • What operation needs to be performed?
    • The function needs to calculate the absolute difference between the highest and lowest sweetness levels at each level of the tree.
  • What should be returned?
    • The function should return a list where each element is the sweetness difference for the corresponding level.
HAPPY CASE
Input: 
    sweetness_levels = [3, 9, 20, None, None, 15, 7]
    chocolate_box = build_tree(sweetness_levels)
Output: 
    [0, 11, 8]
Explanation: 
    The sweetness differences are [0] for the root, [20 - 9 = 11] for the second level, and [15 - 7 = 8] for the third level.

EDGE CASE
Input: 
    sweetness_levels = [5]
    chocolate_box = build_tree(sweetness_levels)
Output: 
    [0]
Explanation: 
    The tree contains only one node, so the difference is 0.

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): A BFS approach is suitable for processing the tree level by level, allowing us to calculate the sweetness differences at each 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, keep track of the minimum and maximum sweetness levels, then calculate and store their difference.

1) If the tree is empty (`chocolates` is `None`), return an empty list.
2) Initialize an empty list `results` to store the sweetness differences for each level.
3) Initialize a queue starting with the root node.
4) While the queue is not empty:
    - Initialize variables `current_min` and `current_max` to track the min and max sweetness levels for the current level.
    - 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.
        - Update `current_min` and `current_max` based on the node's value.
        - If the node has a left child, enqueue the left child.
        - If the node has a right child, enqueue the right child.
    - Calculate the absolute difference between `current_min` and `current_max` and append it to `results`.
5) Return `results`.

⚠️ Common Mistakes

  • Not correctly handling the case where the tree is empty.
  • Forgetting to calculate the difference for the last level after the loop ends.

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 sweet_difference(chocolates):
    if not chocolates:
        return []
    
    results = []
    queue = deque([chocolates])  # Start with the root
    
    while queue:
        level_size = len(queue)
        current_min = float('inf')
        current_max = float('-inf')
        
        for _ in range(level_size):
            node = queue.popleft()
            # Update min and max for the current level
            current_min = min(current_min, node.val)
            current_max = max(current_max, node.val)
            
            # Add child nodes to the queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Append the difference for the current level
        results.append(abs(current_max - current_min))
    
    return results
    
# Example Usage:
sweetness_levels = [3, 9, 20, None, None, 15, 7]
chocolate_box = build_tree(sweetness_levels)

print(sweet_difference(chocolate_box))  # [0, 11, 8]

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: 
        `sweetness_levels = [3, 9, 20, None, None, 15, 7]`
        `chocolate_box = build_tree(sweetness_levels)`
    - Execution: 
        - Perform BFS level by level.
        - Sweetness differences: [0] for root, [11] for second level, [8] for third level.
    - Output: 
        [0, 11, 8]

- Example 2:
    - Input: 
        `sweetness_levels = [5]`
        `chocolate_box = build_tree(sweetness_levels)`
    - Execution: 
        - Only one level with one node.
        - Sweetness difference: [0].
    - Output: 
        [0]

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 sweetness difference 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.