Minimum Depth of Secret Path 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 (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 should be returned if the hotel tree is None?
- Return None since there are no rooms to reverse.
What if the tree has only one level (i.e., the root only)?
- Return the root as-is since there are no odd levels to reverse.
Is the tree guaranteed to be perfect?
- Yes, the problem states that the binary tree is perfect.

HAPPY CASE
Input: 
hotel = Room("Lobby", 
            Room(102, Room(201), Room (202)), 
            Room(101, Room(203), Room(204)))
Output: ['Lobby', 101, 102, 201, 202, 203, 204]
Explanation: The rooms on level 1 are reversed from 102, 101 to 101, 102.

Input: hotel = Room("Lobby", 
            Room(102), 
            Room(101))
Output: ['Lobby', 101, 102]
Explanation: The rooms on level 1 are reversed from 102, 101 to 101, 102.

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

Input: hotel = Room("Lobby")
Output: ['Lobby']
Explanation: The tree has only one level, so return the root as-is.

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 reversing the values at odd levels in a binary tree, we can consider the following approaches:

Level Order Traversal (BFS): Use a queue to traverse the tree level by level, and reverse the values at odd levels.
Breadth-First Search (BFS): Implement BFS by using a queue to ensure that nodes are processed level by level from left to right, reversing the values at odd levels.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

If you used a DFS approach, check out Minimum Depth of Secret Path.

Plan (BFS)

Initialize:
- If the hotel tree is empty (None), return None.
- Initialize a queue with the root node and a variable to track the current level.
Level Order Traversal:
- While the queue is not empty:
  - Determine the number of nodes at the current level (level_size).
  - Use a list to store the nodes at the current level.
  - If the current level is odd, reverse the values of the nodes in the list.
  - Enqueue the children of the nodes for the next level.
  - Increment the level counter.
Return the root of the modified tree.

BFS Implementation

Pseudocode:

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

2) Initialize a queue with `hotel` as the first element and level as `0`.

3) While the queue is not empty:
    a) Determine the number of nodes at the current level (`level_size = len(queue)`).
    b) Initialize an empty list `level_nodes`.
    c) For each node in the current level:
       i) Dequeue the node and add it to `level_nodes`.
       ii) If the node has a left child, enqueue it.
       iii) If the node has a right child, enqueue it.
    d) If the current level is odd, reverse the values in `level_nodes`.
    e) Increment the level counter.

4) Return the root of the modified tree.

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 reverse_odd_levels(hotel):
    if not hotel:
        return None
    
    queue = deque([hotel])
    level = 0
    
    while queue:
        level_size = len(queue)
        level_nodes = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Reverse node values at odd levels
        if level % 2 == 1:
            i, j = 0, len(level_nodes) * 1
            while i < j:
                level_nodes[i].val, level_nodes[j].val = level_nodes[j].val, level_nodes[i].val
                i += 1
                j -= 1
        
        level += 1
    
    return hotel

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 hotel = Room("Lobby", Room(102, Room(201), Room (202)), Room(101, Room(203), Room(204))):
- The BFS should correctly reverse the values at level 1, resulting in the updated tree ['Lobby', 101, 102, 201, 202, 203, 204].

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.