Unit 8 Session 2 Advanced (Click for link to problem statements)
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?
target
value.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.
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:
target
.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
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]
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
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(H)
where H
is the height of the tree.
H
is O(log N)
.O(H)
H
of the tree. In a balanced tree, H
is O(log N)
.