Remove Plant - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

💡 Difficulty: Medium-Hard
⏰ Time to complete: 25-30 mins
🛠️ Topics: Trees, Binary Search Trees, Deletion, Inorder Traversal

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 alphabetically by value.
What operation needs to be performed?
- The function needs to remove a specified node from the BST while maintaining BST properties.
What should be returned?
- The function should return the root of the updated BST.

HAPPY CASE
Input: 
      collection = TreeNode("Monstera", 
                  TreeNode("MoneyTree", None, TreeNode("Pothos")),
                  TreeNode("Pilea", TreeNode("Hoya"), TreeNode("Ivy"))),
      name = "Pilea"
Output: Updated BST with "Pilea" removed, replaced by its inorder predecessor.
Explanation: "Pilea" has two children, so it's replaced by the inorder predecessor "Hoya".

EDGE CASE
Input: 
      collection = TreeNode("Monstera", 
                  TreeNode("MoneyTree", None, TreeNode("Pothos")),
                  TreeNode("Pilea", TreeNode("Hoya"), TreeNode("Ivy"))),
      name = "Monstera"
Output: Updated BST with "Monstera" removed, replaced by its inorder predecessor.
Explanation: "Monstera" is the root with two children, so it's replaced by the inorder predecessor "Pilea".

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:

BST Deletion: Removing a node from a BST while maintaining its properties involves several cases, such as no child, one child, or two children. For the two-child case, the node is replaced by its inorder predecessor.
Inorder Traversal: Utilized to find the inorder predecessor when the node to be removed has two children.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the BST to find the node to remove. Handle the different cases based on the node's children, and update the tree accordingly.

1) If the current node (`collection`) is `None`, return `None`.
2) If `name` is less than the current node's value, recurse on the left subtree.
3) If `name` is greater than the current node's value, recurse on the right subtree.
4) If `name` matches the current node's value:
    - If the node has no children, return `None`.
    - If the node has one child, return that child.
    - If the node has two children:
        - Find the inorder predecessor (rightmost node in the left subtree).
        - Replace the current node's value with the inorder predecessor's value.
        - Recursively remove the inorder predecessor from the left subtree.
5) Return the root of the updated tree.

⚠️ Common Mistakes

Not correctly handling the case where the node to be removed has two children.
Forgetting to update parent pointers when removing a node.

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 remove_plant(collection, name):
    if collection is None:
        return collection
    
    # Step 1: Find the node to be removed
    if name < collection.val:
        collection.left = remove_plant(collection.left, name)
    elif name > collection.val:
        collection.right = remove_plant(collection.right, name)
    else:
        # Node with the same name found
        # Step 2: Node has no children (leaf node)
        if collection.left is None and collection.right is None:
            return None
        
        # Step 3: Node has one child
        if collection.left is None:
            return collection.right
        elif collection.right is None:
            return collection.left
        
        # Step 4: Node has two children
        # Find the inorder predecessor (rightmost node in the left subtree)
        predecessor = max_value_node(collection.left)
        # Replace the node's value with the predecessor's value
        collection.val = predecessor.val
        # Remove the inorder predecessor
        collection.left = remove_plant(collection.left, predecessor.val)
    
    return collection

def max_value_node(node):
    current = node
    while current.right:
        current = current.right
    return current

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("Monstera", TreeNode("MoneyTree", None, TreeNode("Pothos")), TreeNode("Pilea", TreeNode("Hoya"), TreeNode("Ivy")))`
        `name = "Pilea"`
    - Execution: 
        - Start at root "Monstera".
        - "Pilea" > "Monstera", move to the right child "Pilea".
        - Node "Pilea" found with two children, find inorder predecessor "Hoya".
        - Replace "Pilea" with "Hoya" and remove "Hoya".
    - Output: 
    ```
    Monstera
    MoneyTree Hoya
    Pothos Ivy
    ```

- Example 2:
    - Input: 
        `collection = TreeNode("Monstera", TreeNode("MoneyTree", None, TreeNode("Pothos")), TreeNode("Pilea", TreeNode("Hoya"), TreeNode("Ivy")))`
        `name = "Monstera"`
    - Execution: 
        - Start at root "Monstera".
        - Node "Monstera" found with two children, find inorder predecessor "Pilea".
        - Replace "Monstera" with "Pilea" and remove "Pilea".
    - Output: 
    ```
    Pilea
    MoneyTree Hoya
    Pothos Ivy
    ```

6: E-valuate

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

Assume N represents the number of nodes in the tree.

Time Complexity: O(H) where H is the height of the tree. In a balanced BST, this is O(log N).
Space Complexity: O(H) due to the recursive call stack. In the worst case for a skewed tree, this could be O(N).