Croquembouche - 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, BFS

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 is None?
    • Return an empty list since there are no flavors to print.
  • What if the tree has only one node?
    • Return a list containing only that node's flavor.
  • 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 flavors are printed level by level, starting from the root.

Input: croquembouche = Puff("Chocolate")
Output: ['Chocolate']
Explanation: The tree has only one node, so return its flavor.

EDGE CASE
Input: croquembouche = 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 only two nodes, and the second node is on the left.

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 binary trees in level order, we can consider the following approaches:

  • Level Order Traversal (BFS): Use a queue to traverse the tree level by level, appending each node's value to the result list as we go.
  • Breadth-First Search (BFS): The BFS approach is ideal for level order traversal since it processes nodes in the order of their depth from the root.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Initialize:
    • If the design tree is empty, 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:
      • Dequeue the front node from the queue.
      • Append the node's value to the result list.
      • If the node has a left child, enqueue it.
      • If the node has a right child, enqueue it.
  3. Return the result list containing the flavors in level order.

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) Dequeue the first node in the queue.
    b) Append the node's value to the result list.
    c) If the node has a left child, enqueue it.
    d) If the node has a right child, enqueue it.
4) Print the result list.

4: I-mplement

Implement the code to solve the algorithm.

class Puff:
    def __init__(self, flavor, left=None, right=None):
        self.val = flavor
        self.left = left
        self.right = right

def print_design(design):
    if not design:
        return []
    
    queue = deque([design])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    print(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 traversal should correctly output ['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.