Icing Cupcakes in Zigzag Order - 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, Zigzag Traversal

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 cupcakes tree is None?
    • Return an empty list since there are no cupcakes to ice.
  • 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: flavors = ["Chocolate", "Vanilla", "Lemon", "Strawberry", None, "Hazelnut", "Red Velvet"]
Output: ['Chocolate', 'Lemon', 'Vanilla', 'Strawberry', 'Hazelnut', 'Red Velvet']
Explanation: The cupcakes are iced in a zigzag order level by level.

Input: flavors = ["Vanilla"]
Output: ['Vanilla']
Explanation: The tree has only one node, so return its flavor.

EDGE CASE
Input: flavors = []
Output: []
Explanation: The tree is empty, so return an empty list.

Input: flavors = ["Chocolate", "Vanilla", None, "Strawberry"]
Output: ['Chocolate', 'Vanilla', 'Strawberry']
Explanation: The cupcakes are iced in a zigzag order level by level.

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

  • Level Order Traversal (BFS): Use a queue to traverse the tree level by level, and alternate between appending nodes from left to right and right to left.
  • Zigzag Traversal: Implement zigzag traversal by using a deque to handle alternating insertions from either the left or right.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Initialize:
    • If the cupcakes tree is empty (None), return an empty list.
    • Initialize a queue with the root node, an empty result list, and a boolean flag left_to_right to indicate the direction of insertion.
  2. Level Order Traversal:
    • While the queue is not empty:
      • Determine the number of nodes at the current level (level_size).
      • Use a deque to store the node values at the current level in the correct order.
      • For each node in the current level:
        • Dequeue the node.
        • Append or appendleft the node's value to the deque based on the left_to_right flag.
        • Enqueue the node's children.
      • Append the deque to the result list.
      • Toggle the left_to_right flag for the next level.
  3. Return the result list.

Zigzag Traversal Implementation

Pseudocode:

1) If `cupcakes` is `None`, return an empty list.
2) Initialize a queue with `cupcakes` as the first element, an empty result list, and `left_to_right` as `True`.
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 deque `level`.
    c) For each node in the current level:
       i) Dequeue the node.
       ii) Append or appendleft the node's value to `level` based on `left_to_right`.
       iii) Enqueue the node's left and right children if they exist.
    d) Extend the `result` list with `level`.
    e) Toggle the `left_to_right` flag for the next level.
4) Return `result`.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def zigzag_icing_order(cupcakes):
    if not cupcakes:
        return []
    
    result = []
    queue = deque([cupcakes])
    left_to_right = True
    
    while queue:
        level_size = len(queue)
        level = deque()
        
        for _ in range(level_size):
            node = queue.popleft()
            if left_to_right:
                level.append(node.val)
            else:
                level.appendleft(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.extend(level)
        left_to_right = not left_to_right
    
    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 flavors = ["Chocolate", "Vanilla", "Lemon", "Strawberry", None, "Hazelnut", "Red Velvet"]:
    • The BFS with zigzag traversal should correctly return the list ['Chocolate', 'Lemon', 'Vanilla', 'Strawberry', 'Hazelnut', 'Red Velvet'].

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.