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:
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.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, 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
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]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]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)
