Maximum Tiers in Cake II - 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, Breadth-First Search, 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 should be returned if the cake tree is None?
    • Return 0 since there are no tiers in the cake.
  • What if the tree has only one node?
    • Return 1 since the maximum number of tiers is 1.
  • Is the tree guaranteed to be balanced?
    • The problem assumes the input tree is balanced when calculating time complexity.
HAPPY CASE
Input: cake_sections = ["Chocolate", "Vanilla", "Strawberry", None, None, "Chocolate", "Coffee"]
Output: 3
Explanation: The longest path is from "Chocolate" -> "Strawberry" -> "Coffee".

Input: cake_sections = ["Vanilla"]
Output: 1
Explanation: The tree has only one node, so the maximum number of tiers is 1.

EDGE CASE
Input: cake_sections = []
Output: 0
Explanation: The tree is empty, so return 0.

Input: cake_sections = ["Chocolate", "Vanilla", "Strawberry", None, "Raspberry"]
Output: 3
Explanation: The longest path is from "Chocolate" -> "Vanilla" -> "Raspberry".

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 maximum depth of a binary tree using a breadth-first search, we can consider the following approaches:

  • Breadth-First Search (BFS): Use BFS to explore each level of the tree iteratively, counting the levels to determine the depth.
  • Level Order Traversal: Traverse the tree level by level and increment the depth counter for each level processed.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

Note: Like many interview questions, this problem can be solved multiple ways. If you used a recursive, DFS approach, take a look at the Maximum Tiers in Cake solution.

  1. Initialize:
    • If the cake tree is empty (None), return 0.
    • Initialize a queue with the root node and a variable to track the depth (max_tiers).
  2. Breadth-First Search:
    • While the queue is not empty:
      • Determine the number of nodes at the current level (level_size).
      • Process all nodes at this level by dequeuing them and enqueuing their children.
      • Increment the depth counter after processing each level.
  3. Return the depth counter as the maximum number of tiers.

BFS Implementation

Pseudocode:

1) If `cake` is `None`, return `0`.
2) Initialize a queue with `cake` as the first element and `max_tiers` as `0`.
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 has a left child, enqueue it.
       iii) If the node has a right child, enqueue it.
    c) Increment `max_tiers`.
4) Return `max_tiers`.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def max_tiers(cake):
    if not cake:
        return 0
    
    queue = deque([cake])
    max_tiers = 0
    
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        max_tiers += 1
    
    return max_tiers

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 cake_sections = ["Chocolate", "Vanilla", "Strawberry", None, None, "Chocolate", "Coffee"]:
    • The BFS should correctly count the number of levels in the tree and return 3 as the maximum number of tiers.

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.