TIP102 Unit 9 Session 2 Standard (Click for link to problem statements)
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?
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.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:
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
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]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]Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(N) where N is the number of nodes in the tree.
O(N)
