Find Next Order to Fulfill Today - 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.

  • What should be returned if the order_tree is None?
    • Return None since there are no orders to process.
  • What if the order is the last node on its level?
    • Return None since there are no more orders on the same level.
  • Can the order node be assumed to exist in the tree?
    • Yes, the problem assumes that order is a valid node in the tree.
HAPPY CASE
Input: 
cupcakes = TreeNode("Cupcakes")
macaron = TreeNode("Macaron")
cookies = TreeNode("Cookies")
cake = TreeNode("Cake")
eclair = TreeNode("Eclair")
croissant = TreeNode("Croissant")

cupcakes.left, cupcakes.right = macaron, cookies
macaron.right = cake
cookies.left, cookies.right = eclair, croissant

next_order1 = find_next_order(cupcakes, cake)
next_order2 = find_next_order(cupcakes, cookies)

Output: Eclair, None
Explanation: 
* The next order after Cake on the same level is Eclair.
* Cookies is the last order on its level, so return None.

EDGE CASE
Input: order_tree = None, order = None
Output: None
Explanation: The tree is empty, so return None.

Input: order_tree = TreeNode("Cupcakes"), order = TreeNode("Cupcakes")
Output: None
Explanation: There is only one order in the tree, so return None.

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 finding the next node on the same level in a binary tree, we can consider the following approaches:

  • Level Order Traversal (BFS): Use a queue to traverse the tree level by level, checking for the target node and returning the next node on the same level.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Initialize:
    • If the order_tree is empty (None), return None.
    • Initialize a queue with the root node.
  2. Level Order Traversal:
    • While the queue is not empty:
      • Determine the number of nodes at the current level (level_size).
      • For each node in the current level:
        • Dequeue the node and check if it matches the target order.
        • If it matches, check if it's the last node on the level:
          • If so, return None.
          • Otherwise, return the next node in the queue.
        • Enqueue the children of the current node for the next level.
  3. Return None if the target order is not found in the tree.

BFS Implementation

Pseudocode:

1) If `order_tree` is `None`, return `None`.

2) Initialize a queue with `order_tree` as the first element.

3) While the queue is not empty:
    a) Determine the number of nodes at the current level (`level_size = len(queue)`).
    b) For each node in the current level:
       i) Dequeue the node.
       ii) If the node matches `order`, check if it's the last node on the level:
           * If so, return `None`.
           * Otherwise, return the next node in the queue.
       iii) If the node has a left child, enqueue it.
       iv) If the node has a right child, enqueue it.

4) Return `None` if the target `order` is not found in the tree.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def find_next_order(order_tree, order):
    if not order_tree:
        return None
    
    queue = deque([order_tree])
    
    while queue:
        level_size = len(queue)
        
        for i in range(level_size):
            node = queue.popleft()
            
            # Check if this is the node we are currently fulfilling
            if node == order:
                # If it's the last node on the level, return None
                if i == level_size - 1:
                    return None
                else:
                    # The next node in the queue is the next order on the same level
                    return queue.popleft()
            
            # Add children to the queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return None  # If order is not found in the tree

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 order_tree = TreeNode("Cupcakes"), order = TreeNode("Cake"):
    • The BFS should correctly identify the next order after "Cake" as "Eclair" and return it.

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 may need to be visited to find the target node.
  • Space Complexity: O(N) due to the queue storing nodes at each level during traversal.