Croquembouche II - codepath/compsci_guides GitHub Wiki

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'](/codepath/compsci_guides/wiki/'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'](/codepath/compsci_guides/wiki/'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'](/codepath/compsci_guides/wiki/'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'](/codepath/compsci_guides/wiki/'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.