Split Collection - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

💡 Difficulty: Hard
⏰ Time to complete: 30-35 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 tree?
- The tree is a Binary Search Tree (BST) where each node represents a plant in the collection, organized lexicographically.
What operation needs to be performed?
- The function needs to split the tree into two subtrees based on a given target value.
What should be returned?
- The function should return an array of two root nodes: the first subtree containing all nodes with values smaller than or equal to target, and the second subtree containing all nodes with values greater than target.

HAPPY CASE
Input: 
    collection = TreeNode("MoneyTree", TreeNode("Hoya", TreeNode("Aloe"), TreeNode("Ivy")), TreeNode("Pilea", TreeNode("Orchid"), TreeNode("ZZPlant")))
    target = "Hoya"
Output: 
    Left Subtree: TreeNode("Hoya", TreeNode("Aloe"), None)
    Right Subtree: TreeNode("MoneyTree", TreeNode("Ivy"), TreeNode("Pilea", TreeNode("Orchid"), TreeNode("ZZPlant")))
Explanation: 
    The original tree is split into two subtrees based on the target "Hoya".

EDGE CASE
Input: 
    collection = TreeNode("MoneyTree", TreeNode("Hoya", TreeNode("Aloe"), TreeNode("Ivy")), TreeNode("Pilea", TreeNode("Orchid"), TreeNode("ZZPlant")))
    target = "ZZPlant"
Output: 
    Left Subtree: TreeNode("MoneyTree", TreeNode("Hoya", TreeNode("Aloe"), TreeNode("Ivy")), TreeNode("Pilea", TreeNode("Orchid"), None))
    Right Subtree: None
Explanation: 
    The target "ZZPlant" is the largest value in the tree, so all nodes belong to the left subtree.

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:

Recursion: Recursive traversal of the tree is necessary to split the tree into two subtrees while preserving the BST properties.
Divide and Conquer: The problem can be solved by dividing the tree into smaller parts based on the comparison with the target.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Recursively traverse the BST and split it into two subtrees based on the target value. Nodes with values smaller than or equal to target go into the left subtree, and nodes with values greater than target go into the right subtree.

1) If the current node (`collection`) is `None`, return `[None, None]`.
2) If the value of the current node is less than or equal to `target`:
    - Recursively split the right subtree using the same function.
    - Attach the left part of the split right subtree to the current node's right.
    - Return the current node as the root of the left subtree and the right part of the split as the right subtree.
3) If the value of the current node is greater than `target`:
    - Recursively split the left subtree using the same function.
    - Attach the right part of the split left subtree to the current node's left.
    - Return the left part of the split as the left subtree and the current node as the root of the right subtree.

⚠️ Common Mistakes

Not correctly attaching the subtrees after the split.
Failing to preserve the BST properties in the resulting subtrees.

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 split_collection(collection, target):
    if not collection:
        return [None, None]
    
    if collection.val <= target:
        # The current root should be in the left subtree
        left_subtree, right_subtree = split_collection(collection.right, target)
        collection.right = left_subtree  # Attach the left part to the right of the root
        return [collection, right_subtree]
    else:
        # The current root should be in the right subtree
        left_subtree, right_subtree = split_collection(collection.left, target)
        collection.left = right_subtree  # Attach the right part to the left of the root
        return [left_subtree, collection]

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: 
        `collection = TreeNode("MoneyTree", TreeNode("Hoya", TreeNode("Aloe"), TreeNode("Ivy")), TreeNode("Pilea", TreeNode("Orchid"), TreeNode("ZZPlant")))`
        `target = "Hoya"`
    - Execution: 
        - Start at root "MoneyTree".
        - "MoneyTree" > "Hoya", split the left subtree "Hoya".
        - "Hoya" <= "Hoya", split the right subtree "Ivy".
        - Attach "Ivy" to the right of "MoneyTree".
    - Output: 
        Left Subtree: "Hoya -> Aloe"
        Right Subtree: "MoneyTree -> Ivy, Pilea -> Orchid, ZZPlant"

- Example 2:
    - Input: 
        `collection = TreeNode("MoneyTree", TreeNode("Hoya", TreeNode("Aloe"), TreeNode("Ivy")), TreeNode("Pilea", TreeNode("Orchid"), TreeNode("ZZPlant")))`
        `target = "ZZPlant"`
    - Execution: 
        - Start at root "MoneyTree".
        - "MoneyTree" <= "ZZPlant", split the right subtree "Pilea".
        - "Pilea" <= "ZZPlant", split the right subtree "ZZPlant".
        - Attach the resulting left subtree to "Pilea".
    - Output: 
        Left Subtree: "MoneyTree -> Hoya -> Aloe, Ivy, Pilea -> Orchid"
        Right Subtree: None

6: E-valuate

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

Time Complexity:

Time Complexity: O(H) where H is the height of the tree.
- Explanation: The algorithm may need to traverse the height of the tree to perform the split. In a balanced BST, H is O(log N).

Space Complexity:

Space Complexity: O(H)
- Explanation: The recursion stack will use space proportional to the height H of the tree. In a balanced tree, H is O(log N).