Check Bakery Order Completeness - codepath/compsci_guides GitHub Wiki

TIP102 Unit 9 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-25 mins
🛠️ Topics: Trees, BFS, Level Order 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 is the structure of the tree?
- The tree is a binary tree where each node represents a different item in a customer order.
What operation needs to be performed?
- The function needs to check whether the tree representing the order is complete.
What should be returned?
- The function should return True if the order is complete and False otherwise.

HAPPY CASE
Input: 
    items = ["Croissant", "Cupcake", "Bagel", "Cake", "Pie", "Blondies"]
Output: 
    True
Explanation: 
    The tree structure:
        Croissant
       /         \
    Cupcake      Bagel
   /      \      /
Cake     Pie  Blondies
    The order is complete as all levels, except possibly the last, are completely filled, and the last level items are as far left as possible.

EDGE CASE
Input: 
    items = ["Croissant", "Cupcake", "Bagel", "Cake", "Pie", None, "Blondies"]
Output: 
    False
Explanation: 
    The tree structure:
        Croissant
       /         \
    Cupcake      Bagel
   /      \           \
Cake     Pie         Blondies
    The order is not complete because there is a gap in the last level (right child of Bagel without a corresponding left child).

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 Tree Completeness problems, we want to consider the following approaches:

Breadth-First Search (BFS): BFS (or level order traversal) is well-suited for this problem as it allows us to process each level of the tree and detect when an incomplete level is encountered.
Level Order Traversal: This can help in ensuring that all nodes at a certain level are present before proceeding to the next level.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

Perform a BFS on the tree.
During the traversal, if a None node is encountered, mark that any subsequent nodes in the level order must also be None to maintain completeness.
If any node appears after encountering a None, the tree is not complete.

1) Initialize a queue and add the root node to it.
2) Use a variable `encountered_none` to track if a `None` node has been encountered.
3) Perform a BFS traversal:
    - Dequeue the next node.
    - If the node is not `None`, check if `encountered_none` is `True`. If it is, return `False`.
    - Otherwise, add the node's left and right children to the queue (even if they are `None`).
    - If the node is `None`, set `encountered_none` to `True`.
4) If the BFS completes without finding any issues, return `True`.

⚠️ Common Mistakes

Forgetting to account for the possibility of None nodes appearing in between valid nodes.
Not correctly handling the None nodes when traversing through the tree.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def is_complete(root):
    if not root:
        return True
    
    queue = deque([root])
    encountered_none = False
    
    while queue:
        node = queue.popleft()
        
        if node:
            if encountered_none:
                # If we previously encountered a None, and now we see a node, it's not complete
                return False
            queue.append(node.left)
            queue.append(node.right)
        else:
            encountered_none = True
    
    return True

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

- Example 1:
    - Input: 
        `items = ["Croissant", "Cupcake", "Bagel", "Cake", "Pie", "Blondies"]`
    - Execution: 
        - Traverse the tree using BFS, ensuring all levels are complete.
    - Output: 
        True

- Example 2:
    - Input: 
        `items = ["Croissant", "Cupcake", "Bagel", "Cake", "Pie", None, "Blondies"]`
    - Execution: 
        - Traverse the tree using BFS, detect the gap in the last level.
    - Output: 
        False

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

Time Complexity: O(N) where N is the number of nodes in the tree.
- Explanation: Each node is processed exactly once during the BFS traversal.

Space Complexity:

Space Complexity:
- Balanced Tree: O(W) where W is the maximum width of the tree.
  - Explanation: The BFS queue can hold at most the number of nodes at the maximum width of the tree, which is generally O(N/2) in a balanced tree.
- Unbalanced Tree: O(N) where N is the number of nodes.
  - Explanation: In the worst case, the queue might need to hold all nodes in the tree if the tree is skewed.