Mapping a Haunted Hotel 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, Level Order Traversal, Breadth-First Search

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 is None?
    • Return an empty dictionary since there are no rooms to map.
  • Is the binary tree guaranteed to be balanced?
    • The problem assumes the input tree is balanced when calculating time complexity.
  • Are the node values unique?
    • The problem does not specify whether node values are unique, but it does not affect the solution.
HAPPY CASE
Input: 
hotel = Room("Lobby", 
             Room(101, Room(201, Room(301)), Room(202)),
             Room(102, Room(203), Room(204, None, Room(302))))

Output: {
    0: ['Lobby'],
    1: [101, 102],
    2: [201, 202, 203, 204],
    3: [301, 302]
}

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

Input: hotel = Room("Lobby")
Output: {0: ['Lobby']}
Explanation: The tree has only one node, so return a dictionary with one key-value pair.

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 mapping the nodes of a binary tree by level, we can consider the following approaches:

  • Level Order Traversal (BFS): Use a queue to traverse the tree level by level and build the dictionary as we visit nodes.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Initialize:
    • If the hotel is empty (None), return an empty dictionary.
    • Initialize a queue with the root node and its level (0).
    • Initialize an empty dictionary level_map to store the mapping of levels to room values.
  2. Level Order Traversal:
    • While the queue is not empty:
      • Dequeue a node and its corresponding level.
      • If the level is not already in level_map, add it with an empty list.
      • Append the node's value to the list corresponding to its level in level_map.
      • Enqueue the left and right children of the current node with the next level.
  3. Return the level_map dictionary.

BFS Implementation

Pseudocode:

1) If `hotel` is `None`, return an empty dictionary.

2) Initialize a queue with `(hotel, 0)` and an empty dictionary `level_map`.

3) While the queue is not empty:
    a) Dequeue a node and its level.
    b) If `level` is not in `level_map`, add it as a key with an empty list as its value.
    c) Append the node's value to `level_map[level]`.
    d) If the node has a left child, enqueue it with `level + 1`.
    e) If the node has a right child, enqueue it with `level + 1`.

4) Return the `level_map` dictionary.

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 map_hotel(hotel):
    if not hotel:
        return {}
    
    # Initialize the queue and the dictionary
    queue = deque([(hotel, 0)])
    level_map = {}
    
    while queue:
        node, level = queue.popleft()
        
        # Check if the level already exists in the dictionary
        if level not in level_map:
            level_map[level] = []
        
        # Add the current node's value to the corresponding level in the dictionary
        level_map[level].append(node.val)
        
        # Add the children to the queue with the next level
        if node.left:
            queue.append((node.left, level + 1))
        if node.right:
            queue.append((node.right, level + 1))
    
    return level_map

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(101, Room(201, Room(301)), Room(202)), Room(102, Room(203), Room(204, None, Room(302)))):
    • The BFS should correctly map each level of the tree to a list of room values in level_map.

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 to build the level map.
  • Space Complexity: O(N) due to the queue storing nodes at each level during traversal and the level_map dictionary storing the room values.