Organizing Haunted Hallways - codepath/compsci_guides GitHub Wiki

TIP102 Unit 9 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-25 mins
  • 🛠️ Topics: Trees, Binary Search Trees, Recursion

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 is the structure of the data?
    • The data is an integer array sorted in ascending order, where each element represents a unique room number.
  • What operation needs to be performed?
    • The function needs to convert the sorted array into a height-balanced binary search tree (BST).
  • What should be returned?
    • The function should return the root of the constructed BST.
HAPPY CASE
Input: 
    rooms = [4, 7, 13, 666, 1313]
Output: 
    [13, 7, 1313, 4, None, 666]
Explanation: 
    The array is converted into a height-balanced BST as follows:

        13
       /  \
      7    1313 
     /       /
    4       666

EDGE CASE
Input: 
    rooms = [1]
Output: 
    [1]
Explanation: 
    The array contains only one element, so the BST will have a single node.

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 Binary Search Tree (BST) problems, we want to consider the following approaches:

  • Divide and Conquer: Since the array is sorted, we can use the middle element to ensure the BST remains balanced. The left half of the array becomes the left subtree, and the right half becomes the right subtree.
  • Recursion: Recursion is a natural fit for tree problems. We can recursively divide the array and build subtrees.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • To create a height-balanced BST, always select the middle element of the current array (or subarray) as the root node. Recursively apply this logic to the left and right halves of the array to build the left and right subtrees.
1) Define a helper function that takes a subarray defined by its start and end indices.
2) Base Case: If the start index is greater than the end index, return `None`.
3) Calculate the middle index of the current subarray.
4) Create a new `TreeNode` with the value at the middle index.
5) Recursively build the left subtree using the left half of the current subarray.
6) Recursively build the right subtree using the right half of the current subarray.
7) Return the root node of the BST.
8) In the main function, call the helper function with the entire array.

⚠️ Common Mistakes

  • Forgetting to correctly calculate the middle index, especially in cases of even-length arrays.
  • Not correctly handling the base case where the start index is greater than the end index.

4: I-mplement

Implement the code to solve the algorithm.

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

def array_to_bst(rooms):
    if not rooms:
        return None
    
    def build_bst(start, end):
        if start > end:
            return None
        
        mid = (start + end) // 2
        root = TreeNode(rooms[mid])
        root.left = build_bst(start, mid - 1)
        root.right = build_bst(mid + 1, end)
        
        return root
    
    return build_bst(0, len(rooms) - 1)

# Example Usage:
rooms = [4, 7, 13, 666, 1313]
print_tree(array_to_bst(rooms))

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: 
        `rooms = [4, 7, 13, 666, 1313]`
    - Execution: 
        - The middle element is 13, which becomes the root.
        - The left subtree is built from [4, 7] and the right subtree from [666, 1313].
    - Output: 
        [13, 7, 1313, 4, None, 666]

- Example 2:
    - Input: 
        `rooms = [1]`
    - Execution: 
        - The array contains a single element, so the root is 1.
    - Output: 
        [1]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

  • Time Complexity: O(N) where N is the number of elements in the array.
    • Explanation: Each element in the array is visited once to create the BST.

Space Complexity:

  • Space Complexity: O(N) for the recursion stack space in the worst case of an unbalanced tree.
    • Explanation: In a balanced tree, the depth of recursion will be O(log N), but in the worst case of an unbalanced tree, it could be O(N).