TIP102 Unit 9 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?
HAPPY CASE
Input:
rooms = ["Lobby", 101, 123, 201, None, 101, 201, None, None, 201]
Output:
Subtree 1 Subtree 2
101 201
/
201
Explanation:
There are two duplicate subtrees in the given tree.
The first duplicate subtree is rooted at node 101 with a left child 201.
The second duplicate subtree is rooted at node 201.
EDGE CASE
Input:
rooms = ["Lobby", None, None]
Output:
[]
Explanation:
There are no duplicate subtrees in the given tree as the tree only has one node.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 Subtree Identification problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea:
1) Define a helper function `get_id(node)`:
- If `node` is `None`, return 0 (identifier for null nodes).
- Serialize the current subtree by creating a tuple `key` from the node's value and the identifiers of its left and right subtrees.
- Check if `key` is already in the hash map:
- If it is, increment its count.
- If the count reaches 2, add the node to the duplicates list.
- If `key` is not in the hash map, assign it a new identifier and add it to the map.
- Return the identifier for the current subtree.
2) Initialize an empty dictionary `tree_map` to store subtree identifiers and their counts.
3) Initialize an empty list `duplicates` to store the roots of duplicate subtrees.
4) Call `get_id` on the root node to start the traversal.
5) Return the `duplicates` list.⚠️ 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 find_duplicate_subtrees(hotel):
def get_id(node):
if not node:
return 0 # Use 0 as the identifier for null nodes
# Create a unique key for the current subtree
key = (node.val, get_id(node.left), get_id(node.right))
if key in tree_map:
tree_id, count = tree_map[key]
tree_map[key] = (tree_id, count + 1)
else:
tree_id = len(tree_map) + 1
tree_map[key] = (tree_id, 1)
# If this subtree has appeared twice, add it to duplicates
if tree_map[key][1] == 2:
duplicates.append(node)
return tree_map[key][0]
tree_map = {}
duplicates = []
get_id(hotel)
return duplicates
# Example Usage:
rooms = ["Lobby", 101, 123, 201, None, 101, 201, None, None, 201]
hotel = build_tree(rooms)
subtree_lst = find_duplicate_subtrees(hotel)
for subtree in subtree_lst:
print_tree(subtree)Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
- Example 1:
- Input:
`rooms = ["Lobby", 101, 123, 201, None, 101, 201, None, None, 201]`
- Execution:
- Traverse the tree in postorder and serialize each subtree.
- Use the serialized form as a key in the hash map to track duplicates.
- Output:
[Subtree 1: 101 -> 201, Subtree 2: 201]- Example 2:
- Input:
`rooms = ["Lobby", None, None]`
- Execution:
- Traverse the single node tree.
- No duplicates found.
- Output:
[]Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(N) where N is the number of nodes in the tree.
O(N) where N is the number of nodes in the tree.
