Combining Shipwreck Loot

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Trees, Binary Search Trees, Inorder Traversal, Merging Sorted Lists

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 Search Trees (BSTs) where each node represents an item found in a shipwreck, organized in lexicographic (alphabetical) order.
• What operation needs to be performed?
  • The function needs to combine the items from two BSTs into a single list in lexicographic order.
• What should be returned?
  • The function should return a list of all node values from both trees in lexicographic order.

HAPPY CASE
Input: 
    root1 = TreeNode("Fork", TreeNode("Coin"), TreeNode("Statue"))
    root2 = TreeNode("Coin", TreeNode("Anchor"), TreeNode("Mirror"))
Output: 
    ['Anchor', 'Coin', 'Coin', 'Fork', 'Mirror', 'Statue']
Explanation: 
    The values from both trees are combined and sorted in lexicographic order.

EDGE CASE
Input: 
    root3 = TreeNode("Fork", None, TreeNode("Necklace"))
    root4 = TreeNode("Necklace", TreeNode("Fork"))
Output: 
    ['Fork', 'Fork', 'Necklace', 'Necklace']
Explanation: 
    Both trees contain the same items, leading to duplicates in the combined list.

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:

• Inorder Traversal: Perform an inorder traversal of each BST to obtain the items in lexicographic order.
• Merging Sorted Lists: After obtaining two sorted lists from the inorder traversals, merge them into a single sorted list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Perform an inorder traversal on both trees to obtain sorted lists of items. Then merge the two sorted lists into one.

1) Define a helper function `inorder_traversal(root)` that:
    - If the current node is `None`, return an empty list.
    - Recursively traverse the left subtree, add the current node's value to the list, and then traverse the right subtree.
    - Return the combined list.
  
2) Define a function `merge_sorted_lists(list1, list2)` that:
    - Initialize pointers `i` and `j` to the start of `list1` and `list2`.
    - Create an empty list `merged_list`.
    - While both pointers are within the bounds of their respective lists, compare the elements and add the smaller one to `merged_list`.
    - Append any remaining elements from `list1` or `list2` to `merged_list`.
    - Return `merged_list`.
  
3) In the main `combine_loot` function:
    - Perform an inorder traversal on `root1` and `root2` to obtain `list1` and `list2`.
    - Merge `list1` and `list2` using `merge_sorted_lists`.
    - Return the merged list.

⚠️ Common Mistakes

• Not correctly handling duplicates between the two trees.
• Incorrectly merging the two sorted lists, leading to an unsorted final list.

4: I-mplement

Implement the code to solve the algorithm.

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

def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

def merge_sorted_lists(list1, list2):
    i, j = 0, 0
    merged_list = []
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            merged_list.append(list1[i])
            i += 1
        else:
            merged_list.append(list2[j])
            j += 1
    merged_list.extend(list1[i:])
    merged_list.extend(list2[j:])
    return merged_list

def combine_loot(root1, root2):
    list1 = inorder_traversal(root1)
    list2 = inorder_traversal(root2)
    return merge_sorted_lists(list1, list2)

# Example Usage:
root1 = TreeNode("Fork", TreeNode("Coin"), TreeNode("Statue"))
root2 = TreeNode("Coin", TreeNode("Anchor"), TreeNode("Mirror"))

root3 = TreeNode("Fork", None, TreeNode("Necklace"))
root4 = TreeNode("Necklace", TreeNode("Fork"))

print(combine_loot(root1, root2))  # ['Anchor', 'Coin', 'Coin', 'Fork', 'Mirror', 'Statue']
print(combine_loot(root3, root4))  # ['Fork', 'Fork', 'Necklace', 'Necklace']

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: 
        `root1 = TreeNode("Fork", TreeNode("Coin"), TreeNode("Statue"))`
        `root2 = TreeNode("Coin", TreeNode("Anchor"), TreeNode("Mirror"))`
    - Execution: 
        - Perform inorder traversal: list1 = ["Coin", "Fork", "Statue"], list2 = ["Anchor", "Coin", "Mirror"].
        - Merge lists: ["Anchor", "Coin", "Coin", "Fork", "Mirror", "Statue"].
    - Output: 
        ['Anchor', 'Coin', 'Coin', 'Fork', 'Mirror', 'Statue']

- Example 2:
    - Input: 
        `root3 = TreeNode("Fork", None, TreeNode("Necklace"))`
        `root4 = TreeNode("Necklace", TreeNode("Fork"))`
    - Execution: 
        - Perform inorder traversal: list1 = ["Fork", "Necklace"], list2 = ["Fork", "Necklace"].
        - Merge lists: ["Fork", "Fork", "Necklace", "Necklace"].
    - Output: 
        ['Fork', 'Fork', 'Necklace', 'Necklace']

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 root1 and root2, respectively.
  • Explanation: Each node in both trees is visited once during the inorder traversal, and the merging process also takes linear time.

Space Complexity:

• Space Complexity: O(N + M)
  • Explanation: The space is used to store the lists created by the inorder traversals and the merged list. Additionally, the recursion stack uses space proportional to the height of the trees.