Sectioning Off Cursed Zones - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Hard
  • ⏰ Time to complete: 30-35 mins
  • 🛠️ Topics: Trees, Recursion, Lowest Common Ancestor (LCA)

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 tree?
    • The tree is a binary tree where each node represents a room in the hotel.
  • What operation needs to be performed?
    • The function needs to find the smallest subtree that contains all the deepest nodes in the tree.
  • What should be returned?
    • The function should return the root of the smallest subtree containing all the deepest nodes.
HAPPY CASE
Input: 
    rooms = ["Lobby", 101, 102, 201, 202, 203, 204, None, None, "😱", "👻"]
    hotel1 = build_tree(rooms)
Output: 
    [202, '😱', '👻']
Explanation: 
    The subtree rooted at node `202` contains all the deepest nodes "😱" and "👻".

EDGE CASE
Input: 
    rooms = ["Lobby", 101, 102, None, "💀"]
    hotel2 = build_tree(rooms)
Output: 
    ['💀']
Explanation: 
    The deepest node is "💀", so the subtree rooted at "💀" is the smallest subtree containing all deepest nodes.

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 Subtree and Depth Calculation problems, we want to consider the following approaches:

  • Recursion: Recursion is a natural fit for tree problems, allowing us to compute the depth of nodes and determine the Lowest Common Ancestor (LCA) of the deepest nodes.
  • Depth-First Search (DFS): DFS traversal helps explore the entire tree while tracking node depths and potential LCAs.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a recursive function to calculate both the depth of each node and the LCA of the deepest nodes. The smallest subtree containing all deepest nodes will have the root as the LCA of those deepest nodes.

1) Define a helper function `find_depth_and_lca(node)`:
    - If `node` is `None`, return a depth of `0` and `None` as the LCA.
    - Recursively find the depth and LCA of the left subtree (`left_depth`, `left_lca`).
    - Recursively find the depth and LCA of the right subtree (`right_depth`, `right_lca`).
    - The depth of the current node is `1 + max(left_depth, right_depth)`.
    - If `left_depth` equals `right_depth`, then the current node is the LCA of the deepest nodes.
    - If `left_depth` is greater, the LCA is in the left subtree; otherwise, it's in the right subtree.
    - Return the depth of the current node and the LCA.

2) In the main function `smallest_subtree_with_deepest_rooms(hotel)`:
    - Call `find_depth_and_lca(hotel)` and return the LCA obtained from it.

⚠️ Common Mistakes

  • Forgetting to properly calculate and compare depths of subtrees.
  • Not correctly identifying the LCA when depths of subtrees are equal.

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 find_depth_and_lca(node):
    # Base case
    if not node:
        return 0, None
    
    # Recur for left and right subtrees
    left_depth, left_lca = find_depth_and_lca(node.left)
    right_depth, right_lca = find_depth_and_lca(node.right)
    
    # Current node's depth is 1 + max of left and right subtree depths
    current_depth = 1 + max(left_depth, right_depth)
    
    # If left and right depths are equal, current node is the LCA
    if left_depth == right_depth:
        return current_depth, node
    # Otherwise, the LCA is in the subtree with greater depth
    elif left_depth > right_depth:
        return current_depth, left_lca
    else:
        return current_depth, right_lca

def smallest_subtree_with_deepest_rooms(hotel):
    depth, lca = find_depth_and_lca(hotel)
    return lca
    
# Example Usage:
rooms = ["Lobby", 101, 102, 201, 202, 203, 204, None, None, "😱", "👻"]
hotel1 = build_tree(rooms)

rooms = ["Lobby", 101, 102, None, "💀"]
hotel2 = build_tree(rooms)

print_tree(smallest_subtree_with_deepest_rooms(hotel1))  # [202, '😱', '👻']
print_tree(smallest_subtree_with_deepest_rooms(hotel2))  # ['💀']

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 = ["Lobby", 101, 102, 201, 202, 203, 204, None, None, "😱", "👻"]`
        `hotel1 = build_tree(rooms)`
    - Execution: 
        - Perform DFS to find depths of nodes.
        - Identify the LCA of the deepest nodes, which is node `202`.
    - Output: 
        [202, '😱', '👻']

- Example 2:
    - Input: 
        `rooms = ["Lobby", 101, 102, None, "💀"]`
        `hotel2 = build_tree(rooms)`
    - Execution: 
        - Perform DFS to find depths of nodes.
        - Identify the LCA of the deepest nodes, which is node `💀`.
    - Output: 
        ['💀']

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 nodes in the tree.
    • Explanation: Each node is visited exactly once during the DFS traversal to calculate depth and determine the LCA.

Space Complexity:

  • Space Complexity: O(H) where H is the height of the tree.
    • Explanation: The recursion stack will use space proportional to the height of the tree. In a balanced tree, H is O(log N), but in the worst case (skewed tree), it could be O(N).