Flower Finding II - 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 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 tree, but not a binary search tree (BST).
  • How is the tree traversed?
    • The tree must be traversed without leveraging the BST property, so both left and right subtrees need to be checked.
  • What should be returned?
    • The function should return True if the flower is found in the tree, and False otherwise.
HAPPY CASE
Input: ["Daisy", "Lily", "Tulip", "Rose", "Violet", "Lilac"], "Lilac"
Output: True
Explanation: "Lilac" exists in the tree as a node.

EDGE CASE
Input: ["Daisy", "Lily", "Tulip", "Rose", "Violet", "Lilac"], "Sunflower"
Output: False
Explanation: "Sunflower" does not exist in the tree, so the output is `False`.

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 Tree problems, we want to consider the following approaches:

  • Tree Traversal: Since the tree is not a BST, a general traversal method like DFS (Depth-First Search) or BFS (Breadth-First Search) is necessary to check all nodes.
  • Recursion: Recursively explore both the left and right subtrees to ensure the target flower is found if it exists.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Recursively traverse the entire binary tree and check every node to see if it matches the target flower name.

1) If the current node is `None`, return `False`.
2) Check if the current node's value matches the target flower name:
    - If it does, return `True`.
3) Recursively search the left and right subtrees.
4) If either subtree contains the target flower, return `True`; otherwise, return `False`.

⚠️ Common Mistakes

  • Not checking both left and right subtrees, which is necessary because the tree is not a BST.
  • Forgetting to handle the case where the tree is empty.

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 non_bst_find_flower(root, name):
    if root is None:
        return False
    
    if root.val == name:
        return True

    return non_bst_find_flower(root.left, name) or non_bst_find_flower(root.right, name)

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: `garden = TreeNode("Daisy", TreeNode("Lily", TreeNode("Rose"), TreeNode("Violet")), TreeNode("Tulip", None, TreeNode("Lilac")))`, `name = "Lilac"`
    - Execution: 
        - Start at "Daisy", "Lilac" != "Daisy", check both left and right children.
        - Check "Lily", "Lilac" != "Lily", check both left and right children.
        - Check "Tulip", "Lilac" != "Tulip", move to the right child "Lilac".
        - Found "Lilac", return `True`.
    - Output: `True`

- Example 2:
    - Input: `garden = TreeNode("Daisy", TreeNode("Lily", TreeNode("Rose"), TreeNode("Violet")), TreeNode("Tulip", None, TreeNode("Lilac")))`, `name = "Sunflower"`
    - Execution: 
        - Start at "Daisy", "Sunflower" != "Daisy", check both left and right children.
        - Check "Lily", "Sunflower" != "Lily", check both left and right children.
        - Check "Tulip", "Sunflower" != "Tulip", no match found, return `False`.
    - Output: `False`

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.

  1. Time Complexity of non_bst_find_flower():

    • The time complexity is O(N), where N is the number of nodes in the tree.
    • Explanation: In the worst case, the function needs to check every node because the tree is not ordered, requiring an exhaustive search.

  2. Time Complexity of find_flower() from Problem 2:

    • The time complexity is O(H), where H is the height of the tree.
    • Explanation: In a balanced BST, H is O(log N), making the search more efficient by exploiting the BST property.

  3. Unbalanced BST Search:

    • Worst-Case Scenario: If the BST is completely unbalanced (e.g., skewed like a linked list), the time complexity of find_flower() becomes O(N).
    • Explanation: In this scenario, the height H equals the number of nodes N, making the search process as inefficient as searching in a non-BST.