Finding a New Plant Within Budget - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

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

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, with a key indicating the plant's price.
  • What operation needs to be performed?
    • The function needs to find the plant with the highest price below a given budget.
  • What should be returned?
    • The function should return the plant's name if a valid plant is found, or None if no plant fits the budget.
HAPPY CASE
Input: [(50, "FiddleLeafFig"), (25, "Monstera"), (40, "Pothos"), (70, "SnakePlant"), (60, "Fern"), (80, "ZZPlant")], budget = 50
Output: "Pothos"
Explanation: The highest price below 50 is 40, which corresponds to "Pothos".

EDGE CASE
Input: [(50, "FiddleLeafFig"), (25, "Monstera"), (40, "Pothos"), (70, "SnakePlant"), (60, "Fern"), (80, "ZZPlant")], budget = 15
Output: None
Explanation: There is no plant with a price lower than 15, so the output is `None`.

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 Search: Use the properties of the BST to efficiently find the largest key less than the budget.
  • Inorder Traversal: Not needed in this case since we can directly compare keys while traversing the tree.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the BST and keep track of the closest node with a key less than the budget. If the current node's key is less than the budget, it becomes the closest node, and we move to the right child. If the current node's key is greater than or equal to the budget, move to the left child.

1) Initialize a variable `closest` to `None` to keep track of the closest plant.
2) While the current node is not `None`:
    - If the current node's key is less than the budget:
        - Update `closest` to the current node.
        - Move to the right subtree.
    - Otherwise:
        - Move to the left subtree.
3) After the loop, if `closest` is not `None`, return `closest.val`.
4) If `closest` is `None`, return `None`.

⚠️ Common Mistakes

  • Not correctly updating the closest plant.
  • Incorrectly handling cases where no valid plant exists under the given budget.

4: I-mplement

Implement the code to solve the algorithm.

class TreeNode:
    def __init__(self, key, val, left=None, right=None):
        self.key = key      # Plant price
        self.val = val      # Plant name
        self.left = left
        self.right = right

def pick_plant(root, budget):
    closest = None
    
    while root:
        if root.key < budget:
            closest = root
            root = root.right
        else:
            root = root.left
    
    return closest.val if closest else None

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: `inventory = TreeNode(50, "FiddleLeafFig", TreeNode(25, "Monstera", TreeNode(15, "Aloe"), TreeNode(40, "Pothos")), TreeNode(70, "SnakePlant", TreeNode(60, "Fern"), TreeNode(80, "ZZPlant")))`, `budget = 50`
    - Execution: 
        - Start at root (50, "FiddleLeafFig").
        - Key 50 >= budget 50, move to the left child.
        - Key 25 < budget 50, update closest to "Monstera", move to the right child.
        - Key 40 < budget 50, update closest to "Pothos", right child is `None`.
    - Output: `Pothos`

- Example 2:
    - Input: `inventory = TreeNode(50, "FiddleLeafFig", TreeNode(25, "Monstera", TreeNode(15, "Aloe"), TreeNode(40, "Pothos")), TreeNode(70, "SnakePlant", TreeNode(60, "Fern"), TreeNode(80, "ZZPlant")))`, `budget = 15`
    - Execution: 
        - Start at root (50, "FiddleLeafFig").
        - Key 50 >= budget 15, move to the left child.
        - Key 25 >= budget 15, move to the left child.
        - Key 15 >= budget 15, move to the left child, which is `None`.
    - Output: `None`

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 the worst case, this could be O(N) if the tree is skewed.
  • Space Complexity: O(1) because the space usage is constant and does not depend on the size of the input.