Unit 8 Session 2 Standard (Click for link to problem statements)
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.
HAPPY CASE
Input:
ecosystem = TreeNode("Dugong",
TreeNode("BrainCoral", None, TreeNode("Clownfish")),
TreeNode("Lionfish", TreeNode("GiantClam"), TreeNode("Seagrass"))),
name = "Lionfish"
Output: Updated BST with "Lionfish" removed and replaced by its inorder successor.
Explanation: "Lionfish" has two children, so it's replaced by the inorder successor "GiantClam".
EDGE CASE
Input:
ecosystem = TreeNode("Dugong",
TreeNode("BrainCoral", None, TreeNode("Clownfish")),
TreeNode("Lionfish", TreeNode("GiantClam"), TreeNode("Seagrass"))),
name = "Dugong"
Output: Updated BST with "Dugong" removed and replaced by its inorder successor.
Explanation: "Dugong" is the root with two children, so it's replaced by the inorder successor "GiantClam".
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:
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 (`ecosystem`) 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 successor (leftmost node in the right subtree).
- Replace the current node's value with the inorder successor's value.
- Recursively remove the inorder successor from the right subtree.
5) Return the root of the updated tree.
⚠️ 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 remove_species(ecosystem, name):
if not ecosystem:
return None
if name < ecosystem.val:
ecosystem.left = remove_species(ecosystem.left, name)
elif name > ecosystem.val:
ecosystem.right = remove_species(ecosystem.right, name)
else:
# Node to be deleted is found
if not ecosystem.left:
return ecosystem.right
elif not ecosystem.right:
return ecosystem.left
else:
# Node has two children
successor = find_min(ecosystem.left)
ecosystem.val = successor.val
ecosystem.left = remove_species(ecosystem.left, successor.val)
return ecosystem
def find_min(node):
while node.left:
node = node.left
return node
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
- Example 1:
- Input:
`ecosystem = TreeNode("Dugong", TreeNode("BrainCoral", None, TreeNode("Clownfish")), TreeNode("Lionfish", TreeNode("GiantClam"), TreeNode("Seagrass")))`,
`name = "Lionfish"`
- Execution:
- Start at root "Dugong".
- "Lionfish" > "Dugong", move to the right child "Lionfish".
- Node "Lionfish" found with two children, find inorder successor "GiantClam".
- Replace "Lionfish" with "GiantClam" and remove "GiantClam".
- Output:
```
Dugong
BrainCoral GiantClam
Clownfish Seagrass
```
- Example 2:
- Input:
`ecosystem = TreeNode("Dugong", TreeNode("BrainCoral", None, TreeNode("Clownfish")), TreeNode("Lionfish", TreeNode("GiantClam"), TreeNode("Seagrass")))`,
`name = "Dugong"`
- Execution:
- Start at root "Dugong".
- Node "Dugong" found with two children, find inorder successor "GiantClam".
- Replace "Dugong" with "GiantClam" and remove "GiantClam".
- Output:
```
GiantClam
BrainCoral Lionfish
Clownfish Seagrass
```
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.
O(H)
where H
is the height of the tree. In a balanced BST, this is O(log N)
.O(H)
due to the recursive call stack. In the worst case for a skewed tree, this could be O(N)
.