Croquembouche II

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

Problem Highlights

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

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

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

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

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.

BFS Implementation

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.

4: I-mplement

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

5: R-eview

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']].

6: E-valuate

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.