Largest Pumpkin in Each Row - codepath/compsci_guides GitHub Wiki

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

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 pumpkin in the patch, and each node value represents the pumpkin's size.
  • What operation needs to be performed?
    • The function needs to find the largest pumpkin in each row of the tree.
  • What should be returned?
    • The function should return an array of the largest pumpkin sizes in each row.
HAPPY CASE
Input: 
    pumpkin_sizes = [1, 3, 2, 5, 3, None, 9]
    pumpkin_patch = build_tree(pumpkin_sizes)
Output: 
    [1, 3, 9]
Explanation: 
    The largest pumpkins in each row are 1, 3, and 9, respectively.

EDGE CASE
Input: 
    pumpkin_sizes = [7]
    pumpkin_patch = build_tree(pumpkin_sizes)
Output: 
    [7]
Explanation: 
    There is only one row with a single pumpkin of size 7.

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 Level Order Traversal problems, we want to consider the following approaches:

  • Breadth-First Search (BFS): BFS is ideal for level-order traversal of the tree, allowing us to visit all nodes on each level before moving to the next.
  • Queue Data Structure: Using a queue can help manage the nodes at each level efficiently.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a BFS approach to traverse the tree level by level. For each level, track the maximum value of the nodes. Append the maximum value to the result list after processing all nodes at that level.

1) Define a function `largest_pumpkins(pumpkin_patch)`:
    - If `pumpkin_patch` is `None`, return an empty list.
    - Initialize an empty list `result` to store the largest pumpkin sizes.
    - Initialize a queue with the root node of the tree.
    - While the queue is not empty:
        - Determine the number of nodes at the current level (`level_size`).
        - Initialize a variable `max_val` to negative infinity to track the maximum pumpkin size at this level.
        - For each node in the current level:
            - Dequeue a node and update `max_val` if the node's value is greater.
            - Enqueue the left and right children of the node if they exist.
        - Append `max_val` to the `result` list.
    - Return `result`.

⚠️ Common Mistakes

  • Forgetting to handle the case where the tree is empty.
  • Not properly updating the maximum value for each level.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

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

def largest_pumpkins(pumpkin_patch):
    if not pumpkin_patch:
        return []
    
    result = []
    queue = deque([pumpkin_patch])
    
    while queue:
        level_size = len(queue)
        max_val = float('-inf')  # Initialize to negative infinity for comparison
        
        for _ in range(level_size):
            node = queue.popleft()
            max_val = max(max_val, node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(max_val)
    
    return result
    
# Example Usage:
pumpkin_sizes = [1, 3, 2, 5, 3, None, 9]
pumpkin_patch = build_tree(pumpkin_sizes)

print(largest_pumpkins(pumpkin_patch))  # [1, 3, 9]

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: 
        `pumpkin_sizes = [1, 3, 2, 5, 3, None, 9]`
        `pumpkin_patch = build_tree(pumpkin_sizes)`
    - Execution: 
        - Perform BFS to traverse the tree level by level.
        - Track the maximum pumpkin size at each level.
    - Output: 
        [1, 3, 9]

- Example 2:
    - Input: 
        `pumpkin_sizes = [7]`
        `pumpkin_patch = build_tree(pumpkin_sizes)`
    - Execution: 
        - Perform BFS to traverse the tree level by level.
        - Track the maximum pumpkin size at each level.
    - Output: 
        [7]

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 visited exactly once during the BFS traversal.

Space Complexity:

  • Space Complexity: O(W) where W is the maximum width of the tree.
    • Explanation: The queue may hold up to W nodes at the widest level of the tree.