Monstera Madness - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Easy-Medium
  • ⏰ Time to complete: 15-20 mins
  • 🛠️ Topics: Trees, Recursion

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the tree structure?
    • A: The tree is a binary tree, meaning each node has at most two children.
  • Q: What is the value of the tree nodes?
    • A: Each node represents the number of splits in a leaf of a Monstera plant.
  • Q: What should be returned?
    • A: The number of Monstera leaves that have an odd number of splits should be returned.
HAPPY CASE
Input: [2, 3, 5, 6, 7, None, 12]
Output: 3
Explanation: Nodes with odd values are 3, 5, and 7. Hence, 3 leaves have odd splits.

EDGE CASE
Input: None
Output: 0
Explanation: An empty tree should return 0 since there are no leaves to count.

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

  • Recursion: Since this problem involves traversing a tree, a recursive solution would be a natural fit.
  • DFS/BFS: Either Depth-First Search (DFS) or Breadth-First Search (BFS) could be used to traverse the tree, although DFS is typically easier to implement recursively.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the binary tree using recursion and count the number of nodes that have an odd value.

1) If the root is `None`, return `0`.
2) Recursively traverse the left and right subtrees to count the odd splits in each.
3) Check if the current node's value is odd:
   - If odd, add 1 to the count from left and right subtrees.
   - If even, simply return the sum of counts from left and right subtrees.
4) Return the final count.

⚠️ Common Mistakes

  • Forgetting to handle the case where the tree is empty.
  • Not correctly identifying and counting the nodes with odd values.

4: I-mplement

Implement the code to solve the algorithm.

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

def count_odd_splits(root):
    if root is None:
        return 0
    
    left_count = count_odd_splits(root.left)
    right_count = count_odd_splits(root.right)
    
    # Check if the current node has an odd value
    if root.val % 2 != 0:
        return 1 + left_count + right_count
    else:
        return left_count + right_count

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: `root = TreeNode(2, TreeNode(3, TreeNode(6), TreeNode(7)), TreeNode(5, None, TreeNode(12)))`
    - Execution: 
        - The root node `2` is even, so we continue to its children.
        - The left child `3` is odd, so we count it and move to its children.
        - `6` is even, `7` is odd. Add to count.
        - The right child `5` is odd, so we count it and move to its child `12`.
        - `12` is even.
    - Output: `3` (nodes with odd splits are 3, 7, and 5)

- Example 2:
    - Input: `root = None`
    - Execution: Returns 0 immediately.
    - Output: `0`

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 we traverse each node exactly once.
  • Space Complexity: O(H) where H is the height of the tree, due to the recursive call stack.