Haunted Mirror

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, Tree Comparison

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 trees?
  • The trees are binary trees where each node represents an object the vampire is trying to see in the mirror.
• What operation needs to be performed?
  • The function needs to determine whether one tree can be transformed into another by swapping the left and right subtrees any number of times.
• What should be returned?
  • The function should return True if the first tree can be rearranged to match the second tree, and False otherwise.

HAPPY CASE
Input: 
    body_parts = ["🧛‍♂️", "💪🏼", "🤳", "👟", None, None, "👞"]
    vampire = build_tree(body_parts)
Output: 
    ['🧛‍♂️', '🤳', '💪🏼', '👞', None, None, '👟']
Explanation: 
    The tree is mirrored by swapping the left and right children of all nodes.

EDGE CASE
Input: 
    spooky_objects = ["🎃", "😈", "🕸️", None, None, "🧟‍♂️", "👻"]
    spooky_tree = build_tree(spooky_objects)
Output: 
    ['🎃', '🕸️', '😈', '👻', '🧟‍♂️']
Explanation: 
    The tree is mirrored by swapping the left and right children of all 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 Tree Comparison problems, we want to consider the following approaches:

• Recursion: Recursion is a natural fit for tree problems, allowing us to break down the problem into smaller subproblems (e.g., comparing subtrees).
• Tree Traversal: Traversal methods (preorder, inorder, postorder) can be used to systematically compare tree structures.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Recursively check whether two trees are identical, either directly or when one tree is a mirror image of the other. We compare the current nodes, then check both the direct and swapped matches of their subtrees.

1) Define a recursive function `mirror_tree(order1, order2)`:
    - If both `order1` and `order2` are `None`, return `True` (both trees are empty).
    - If one is `None` and the other is not, return `False` (one tree is empty).
    - If the values of `order1` and `order2` do not match, return `False`.
    - Recursively check if the left and right subtrees can be matched:
        - First, check if the left subtree of `order1` matches the left subtree of `order2` and the right subtree of `order1` matches the right subtree of `order2`.
        - Second, check if the left subtree of `order1` matches the right subtree of `order2` and the right subtree of `order1` matches the left subtree of `order2`.
    - Return `True` if either condition holds, otherwise return `False`.

⚠️ Common Mistakes

• Forgetting to check both the direct match and the swapped match of subtrees.
• Not handling the base cases where one or both subtrees are None.

4: I-mplement

Implement the code to solve the algorithm.

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

def mirror_tree(order1, order2):
    # Base cases
    if not order1 and not order2:
        return True
    if not order1 or not order2:
        return False
    if order1.val != order2.val:
        return False
    
    # Check if the subtrees can be matched directly or by swapping
    return (
        (mirror_tree(order1.left, order2.left) and 
         mirror_tree(order1.right, order2.right)) or
        (mirror_tree(order1.left, order2.right) and 
         mirror_tree(order1.right, order2.left))
    )
    
# Example Usage:
flavors1 = ["Red Velvet", "Vanilla", "Lemon", "Ube", "Almond", "Chai", "Carrot", None, None, None, None, "Chai", "Maple", None, "Smore"]
flavors2 = ["Red Velvet", "Lemon", "Vanilla", "Carrot", "Chai", "Almond", "Ube", "Smore", None, "Maple", "Chai"]
order1 = build_tree(flavors1)
order2 = build_tree(flavors2)

print(mirror_tree(order1, order2))  # True

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: 
        `flavors1 = ["Red Velvet", "Vanilla", "Lemon", "Ube", "Almond", "Chai", "Carrot", None, None, None, None, "Chai", "Maple", None, "Smore"]`
        `flavors2 = ["Red Velvet", "Lemon", "Vanilla", "Carrot", "Chai", "Almond", "Ube", "Smore", None, "Maple", "Chai"]`
        `order1 = build_tree(flavors1)`
        `order2 = build_tree(flavors2)`
    - Execution: 
        - Recursively check each subtree.
        - Subtrees can be rearranged to match.
    - Output: 
        True

- Example 2:
    - Input: 
        `flavors1 = ["Red Velvet"]`
        `flavors2 = ["Chocolate"]`
        `order1 = build_tree(flavors1)`
        `order2 = build_tree(flavors2)`
    - Execution: 
        - Root values do not match.
    - Output: 
        False

6: E-valuate

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

Time Complexity:

• Time Complexity: O(N * M) where N and M are the number of nodes in order1 and order2, respectively.
  • Explanation: Each node in order1 may need to be compared with each node in order2 in the worst case.

Space Complexity:

• Space Complexity: O(H1 + H2) where H1 and H2 are the heights of the two trees.
  • Explanation: The recursion stack space depends on the height of the trees.