Unit 9 Session 1 (Click for link to problem statements)

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20 mins
• 🛠️ Topics: Binary Trees, Level Order Traversal, Breadth-First Search

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 should be returned if the design tree is None?
  • Return an empty list since there are no cream puffs to list.
• What if the tree has only one node?
  • Return a list containing one inner list with the flavor of that node.
• Is the tree guaranteed to be balanced?
  • The problem assumes the input tree is balanced when calculating time complexity.

HAPPY CASE Input: croquembouche = Puff("Vanilla", Puff("Chocolate", Puff("Vanilla"), Puff("Matcha")), Puff("Strawberry")) Output: [['Vanilla'], ['Chocolate', 'Strawberry'], ['Vanilla', 'Matcha']] Explanation: The tree is traversed level by level, with each tier represented as an inner list. Input: croquembouche = Puff("Vanilla") Output: [['Vanilla']] Explanation: The tree has only one node, so return a list with one inner list containing its value. EDGE CASE Input: design = None Output: [] Explanation: The tree is empty, so return an empty list. Input: croquembouche = Puff("Vanilla", Puff("Chocolate"), None) Output: [['Vanilla'], ['Chocolate']] Explanation: The tree has two levels, with the second level containing only one 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 problems involving traversing a binary tree level by level and returning a list of lists representing each level, we can consider the following approaches:

• Level Order Traversal (BFS): Use a queue to traverse the tree level by level, collecting nodes into lists based on their level.

Plan the solution with appropriate visualizations and pseudocode.

1. Initialize:
   • If the design tree is empty (None), return an empty list.
   • Initialize a queue with the root node and an empty result list.
2. Level Order Traversal:
   • While the queue is not empty:
     • Determine the number of nodes at the current level (level_size).
     • Use a list to store the nodes at the current level.
     • For each node in the current level:
       • Dequeue the node.
       • Append its value to the current level's list.
       • Enqueue its children for the next level.
     • Append the current level's list to the result list.
3. Return the result list containing the flavors tier by tier.

Pseudocode:

1) If `design` is `None`, return an empty list. 2) Initialize a queue with `design` as the first element and an empty result list. 3) While the queue is not empty: a) Determine the number of nodes at the current level (`level_size = len(queue)`). b) Initialize an empty list `level`. c) For each node in the current level: i) Dequeue the node and add its value to `level`. ii) If the node has a left child, enqueue it. iii) If the node has a right child, enqueue it. d) Append `level` to the result list. 4) Return the result list.

Implement the code to solve the algorithm.

from collections import deque class Puff: def __init__(self, flavor, left=None, right=None): self.val = flavor self.left = left self.right = right def listify_design(design): if not design: return [] result = [] queue = deque([design]) while queue: level_size = len(queue) level = [] for _ in range(level_size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Trace through your code with the input croquembouche = Puff("Vanilla", Puff("Chocolate", Puff("Vanilla"), Puff("Matcha")), Puff("Strawberry")):
  • The BFS should correctly traverse the tree and return the list of lists representing each tier: [['Vanilla'], ['Chocolate', 'Strawberry'], ['Vanilla', 'Matcha']].

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the tree.

• Time Complexity: O(N) because each node in the tree must be visited once.
• Space Complexity: O(N) due to the queue storing nodes at each level during traversal.