Step by Step Directions to Hotel Room - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 25-30 mins
🛠️ Topics: Trees, Pathfinding, 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 shortest path from a starting room to a destination room and return the directions as a string.
What should be returned?
- The function should return a string consisting of 'L', 'R', and 'U', representing the directions from the start node to the destination node.

HAPPY CASE
Input: 
    room_nums = [5, 1, 2, 3, None, 6, 4]
    start_value = 3
    dest_value = 6
Output: 
    "UURL"
Explanation: 
    The shortest path is: 3 -> 1 -> 5 -> 2 -> 6

EDGE CASE
Input: 
    room_nums = [2, 1]
    start_value = 2
    dest_value = 1
Output: 
    "L"
Explanation: 
    The shortest path is: 2 -> 1

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 Tree Pathfinding problems, we want to consider the following approaches:

Lowest Common Ancestor (LCA): Identify the lowest common ancestor of the start and destination nodes to determine the point where the paths diverge.
Depth-First Search (DFS): DFS can be used to trace the path from the root to any specific node.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

Find the path from the root to the start node and the path from the root to the destination node using DFS.
Identify the lowest common ancestor (LCA) by comparing the two paths.
Calculate the directions by moving up from the start node to the LCA and then moving down to the destination node.

1) Define a helper function `find_path(root, target, path)`:
    - Base Case: If `root` is `None`, return `False`.
    - If `root.val` equals the target, return `True`.
    - Recur for the left subtree by appending 'L' to the path. If successful, return `True`.
    - Recur for the right subtree by appending 'R' to the path. If successful, return `True`.
    - If the target is not found, backtrack by popping the last direction and return `False`.

2) In the main function `get_directions(root, start_value, dest_value)`:
    - Use `find_path` to determine the path from the root to the start node and the path from the root to the destination node.
    - Identify the LCA by comparing the paths until they diverge.
    - Calculate the directions by adding 'U' for each step back to the LCA and then appending the directions to the destination node.
    - Return the resulting direction string.

⚠️ Common Mistakes

Failing to correctly identify the LCA, which is crucial for determining the correct directions.
Not handling cases where the start and destination nodes are the same, resulting in an empty path.

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_path(root, target, path):
    if not root:
        return False
    
    if root.val == target:
        return True
    
    # Try to find the target in the left subtree
    path.append('L')
    if find_path(root.left, target, path):
        return True
    path.pop()  # Backtrack if not found
    
    # Try to find the target in the right subtree
    path.append('R')
    if find_path(root.right, target, path):
        return True
    path.pop()  # Backtrack if not found
    
    return False

def get_directions(root, start_value, dest_value):
    start_path = []
    dest_path = []
    
    # Find paths from the root to the start and destination nodes
    find_path(root, start_value, start_path)
    find_path(root, dest_value, dest_path)
    
    # Find the lowest common ancestor (LCA)
    i = 0
    while i < len(start_path) and i < len(dest_path) and start_path[i] == dest_path[i]:
        i += 1
    
    # 'U' moves to go up from start to LCA
    directions = 'U' * (len(start_path) - i)
    
    # Append the remaining path to the destination
    directions += ''.join(dest_path[i:])
    
    return directions

# Example Usage:
room_nums = [5, 1, 2, 3, None, 6, 4]
hotel1 = build_tree(room_nums)
print(get_directions(hotel1, 3, 6))  # Output: "UURL"

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: 
        `room_nums = [5, 1, 2, 3, None, 6, 4]`
        `start_value = 3`
        `dest_value = 6`
    - Execution: 
        - Find the paths to 3 and 6.
        - Identify the LCA (node 5).
        - Construct directions: "UURL".
    - Output: 
        "UURL"

- Example 2:
    - Input: 
        `room_nums = [2, 1]`
        `start_value = 2`
        `dest_value = 1`
    - Execution: 
        - Find the paths to 2 and 1.
        - Identify the LCA (node 2).
        - Construct directions: "L".
    - Output: 
        "L"

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: The DFS traversal is used to find the paths, which takes linear time.

Space Complexity:

Space Complexity: O(H) where H is the height of the tree.
- Explanation: The space complexity is due to the recursion stack and the path lists, which can grow up to the height of the tree.