Mapping a Haunted Hotel - codepath/compsci_guides GitHub Wiki

"Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 15 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 tree is None?
    • Return an empty list since there are no rooms to explore.
  • What if the tree has only one node?
    • Return a list containing only that node's value.
  • Is the tree guaranteed to be balanced?
    • The problem assumes the input tree is balanced when calculating time complexity.
HAPPY CASE
Input: 
hotel = Room("Lobby", 
                Room(101, Room(201, Room(301)), Room(202)),
                Room(102, Room(203), Room(204, None, Room(302))))
Output: ['Lobby', 101, 102, 201, 202, 203, 204, 301, 302]
Explanation: The rooms are explored level by level from left to right.

Input: hotel = Room("Lobby")
Output: ['Lobby']
Explanation: The tree has only one node, so return its value.

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

Input: hotel = Room("Lobby", Room(101))
Output: ['Lobby', 101]
Explanation: The tree has only two nodes, with one child on the left.

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 traversing a binary tree in level order, we can consider the following approaches:

  • Level Order Traversal (BFS): Use a queue to traverse the tree level by level, appending each node's value to the result list as we go.
  • Breadth-First Search (BFS): Implement BFS by using a queue to ensure that nodes are processed level by level from left to right.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Initialize:
    • If the hotel tree is empty (None), return an empty list.
    • Initialize a queue with the root node and an empty result list.
  2. Level Order Traversal:
    • While the queue is not empty:
      • Dequeue the front node from the queue.
      • Append the node's value to the result list.
      • If the node has a left child, enqueue it.
      • If the node has a right child, enqueue it.
  3. Return the result list containing the room values in level order.

BFS Implementation

Pseudocode:

1) If `hotel` is `None`, return an empty list.
2) Initialize a queue with `hotel` as the first element and an empty result list.
3) While the queue is not empty:
    a) Dequeue the first node in the queue.
    b) Append the node's value to the result list.
    c) If the node has a left child, enqueue it.
    d) If the node has a right child, enqueue it.
4) Return the result list.

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 []
    
    result = []
    queue = deque([hotel])
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

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 explore the tree level by level and return the list ['Lobby', 101, 102, 201, 202, 203, 204, 301, 302].

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.