Kth Spookiest Room in the Hotel

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20 mins
• 🛠️ Topics: Binary Search Tree, Inorder 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 root is None?
  • Return None or a similar indication that there is no such room.
• What if k is greater than the number of nodes in the tree?
  • Return None or raise an appropriate error.
• Is the tree guaranteed to be a binary search tree (BST)?
  • Yes, the problem assumes the input tree is a BST.

HAPPY CASE
Input: 
hotel1 = build_tree([(3, "Lobby"), (1, 101), (4, 102), None, (2, 201)])
Output: 101
Explanation: The room with key 1 (spookiest) is room 101.

Input: 
hotel2 = build_tree([(5, 'Lobby'), (3, 101), (6, 102), (2, 201), (4, 202), None, None, (1, 301)])
Output: 101
Explanation: The room with key 3 is room 101.

EDGE CASE
Input: root = None, k = 1
Output: None
Explanation: The tree is empty, so there is no such room.

Input: root = build_tree([(3, "Lobby"), (1, 101), (4, 102)]), k = 5
Output: None
Explanation: k is greater than the number of nodes, so return None.

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 finding the k-th smallest element in a binary search tree (BST), we can consider the following approaches:

• Inorder Traversal: Use inorder traversal to traverse the tree in sorted order and count the nodes until reaching the k-th smallest element.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

1. Base Case:
   • If the root is None, return None.
2. Inorder Traversal:
   • Implement an inorder traversal that traverses the left subtree, visits the root, and then traverses the right subtree.
   • Use a counter to track the number of nodes visited during the traversal.
   • When the counter equals k, return the value of the current node.
3. Return the value of the k-th smallest node after completing the traversal.

Inorder Traversal Implementation

Pseudocode:

1) Define the base case:
   * If the node is `None`, return `None`.

2) Traverse the left subtree.

3) Increment the counter and check if it equals `k`.
   * If so, return the current node's value.

4) Traverse the right subtree.

4: I-mplement

Implement the code to solve the algorithm.

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

def kth_spookiest(root, k):
    def inorder(node):
        if not node:
            return None
        
        # Traverse the left subtree
        left = inorder(node.left)
        if left is not None:
            return left
        
        # Increment the count when visiting the node
        nonlocal count
        count += 1
        if count == k:
            return node.val
        
        # Traverse the right subtree
        return inorder(node.right)
    
    count = 0
    return inorder(root)

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 hotel1 = build_tree([(3, "Lobby"), (1, 101), (4, 102), None, (2, 201)]):
  • The inorder traversal should correctly identify the room with key 1 (spookiest) as room 101.

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) in the worst case because we may need to visit all nodes to find the k-th smallest element.
• Space Complexity: O(H) where H is the height of the tree, due to the recursive call stack.