Icing Cupcakes in Zigzag Order

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