Add New Treasure to Collection - 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: Easy-Medium
  • ⏰ Time to complete: 15-20 mins
  • 🛠️ Topics: Trees, Binary Search Trees, Insertion

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the structure of the tree?
    • A: The tree is a Binary Search Tree (BST) where each node represents an item in Ariel's collection.
  • Q: What operation needs to be performed?
    • A: The function needs to insert a new item into the BST while maintaining the BST properties.
  • Q: What should be returned?
    • A: The function should return the root of the modified tree. If the item already exists, the original tree should be returned unmodified.
HAPPY CASE
Input: 
      grotto = TreeNode("Snarfblat", TreeNode("Gadget", TreeNode("Dinglehopper"), TreeNode("Gizmo")), TreeNode("Whatzit", None, TreeNode("Whozit"))), 
      new_item = "Thingamabob"
Output: Updated BST with "Thingamabob" added in the correct position.
Explanation: "Thingamabob" is added as the left child of "Whatzit".

EDGE CASE
Input: 
      grotto = TreeNode("Snarfblat", TreeNode("Gadget", TreeNode("Dinglehopper"), TreeNode("Gizmo")), TreeNode("Whatzit", None, TreeNode("Whozit"))), 
      new_item = "Gizmo"
Output: The original BST since "Gizmo" already exists in the tree.
Explanation: No changes are made because "Gizmo" is already in the tree.

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 Insertion: The problem requires inserting a new node into a BST, which involves finding the correct position to maintain the tree's ordered structure.
  • Recursion: A recursive approach can be used to traverse the tree and insert the new node at the correct position.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the BST to find the appropriate location for the new item based on its alphabetical order. Insert the new node while maintaining the BST properties.

1) If the current node (`grotto`) is `None`, create a new `TreeNode` with the given `new_item`.
2) If `new_item` is equal to the current node's value, return the current node (no insertion needed as the item already exists).
3) If `new_item` is less than the current node's value, recurse on the left subtree.
4) If `new_item` is greater than the current node's value, recurse on the right subtree.
5) After the recursive call, return the current node to link the updated subtree to the original tree.
6) Return the root of the updated tree.

⚠️ Common Mistakes

  • Forgetting to handle the case where the tree is empty.
  • Not properly returning the updated root after insertion.
  • Not correctly handling the case where the item already exists in the tree.

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 add_treasure(grotto, new_item):
    if not grotto:
        return TreeNode(new_item)
    
    if new_item == grotto.val:
        return grotto  # Item already exists, return the original tree
    elif new_item < grotto.val:
        grotto.left = add_treasure(grotto.left, new_item)
    else:  # new_item > grotto.val
        grotto.right = add_treasure(grotto.right, new_item)
    
    return grotto

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: 
        `grotto = TreeNode("Snarfblat", TreeNode("Gadget", TreeNode("Dinglehopper"), TreeNode("Gizmo")), TreeNode("Whatzit", None, TreeNode("Whozit")))`, 
        `new_item = "Thingamabob"`
    - Execution: 
        - Start at root "Snarfblat".
        - "Thingamabob" > "Snarfblat", move to the right child "Whatzit".
        - "Thingamabob" < "Whatzit", left child is `None`, insert "Thingamabob".
    - Output: 
    ```
               Snarfblat
            /             \
        Gadget            Whatzit
       /     \           /       \
Dinglehopper Gizmo  Thingamabob  Whozit
    ```

- Example 2:
    - Input: 
        `grotto = TreeNode("Snarfblat", TreeNode("Gadget", TreeNode("Dinglehopper"), TreeNode("Gizmo")), TreeNode("Whatzit", None, TreeNode("Whozit")))`, 
        `new_item = "Gizmo"`
    - Execution: 
        - Start at root "Snarfblat".
        - "Gizmo" < "Snarfblat", move to the left child "Gadget".
        - "Gizmo" > "Gadget", move to the right child "Gizmo".
        - "Gizmo" == "Gizmo", item already exists, return the original tree.
    - Output: The original tree remains unchanged.

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. For a balanced BST, H is O(log N), so the insertion operation 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).