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: [1]
/ \
[2] [5]
/ \ \
[3] [4] [6]
/ \
[5] [2]
/ \
[3] [4]
Output: [2] and all its subtrees ([3] and [4]) are duplicate subtrees found in the input tree, so we should return pointers to one of the [2] nodes, one of the [3] nodes, and
/ \ one of the [4] nodes.
[3] [4]
EDGE CASE
Input: NULL
Output: Since there are no nodes passed in, we should return NULL
(this would be a good clarifying question to ask your interviewer).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 trees, some things we should consider are:
Plan the solution with appropriate visualizations and pseudocode.
Setup: create a dictionary that maps node values to nodes to ids
1) Traverse the tree
2) When we visit a node, generate its ID to be (node.val, ID(node.left), ID(node.right))
- the ids of the left and right children are computed recursively
- Save the mapping of a node to its ID in a dictionary
3) Traverse the tree again, storing IDs as we go
- When we come across a node whose ID we have already stored, add the corresponding node to the result array
- Be careful here to make sure we don't add a node that is a duplicate match (we can track a set of IDs
that correspond to nodes that have already been added, and only add a node if its ID is not in this set)⚠️ Common Mistakes
However, since the children's ID are used to define the parent node's ID, this tuple could contain something like this:
Be careful not to put duplicate subtree matches in the result array
Implement the code to solve the algorithm.
class Solution {
Set<TreeNode> set;
Map<String, TreeNode> map;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
set = new HashSet<>();
map = new HashMap<>();
traverse(root);
List<TreeNode> ans = new LinkedList<>();
for (TreeNode node : set) {
ans.add(node);
}
return ans;
}
public String traverse(TreeNode root) {
if (root == null) {
return ";
}
String left = traverse(root.left);
String right = traverse(root.right);
String cur = left +" "+ right +" "+ root.val;
if (map.containsKey(cur)) {
set.add(map.get(cur));
} else {
map.put(cur, root);
}
return cur;
}
} def findDuplicateSubtrees(root: TreeNode) -> List[TreeNode]:
def createIDs(node, ids):
if not node:
return None
# A node's id will be a tuple of its value, the ID of its left child, and the id of its right child
newId = (node.val, createIDs(node.left, ids), createIDs(node.right, ids))
# store ID in the dictionary
ids[node] = newId
# return the ID so the parent node can access it
return newId
# Create dictionary of ids
ids = {}
createIDs(root, ids)
# result set will store the answer
result = set()
# seenIDs will store IDs we have seen to detect duplicates
seenIDs = set()
# addedIDs will store IDs of nodes in result, so we can ensure we don't add duplicates
addedIDs = set()
for node, id in ids.items():
# if an id has already been seen and a node with the same ID has not already been added to the result
# then we can add to the result
if id in seenIDs and id not in addedIDs:
result.add(node)
addedIDs.add(id)
else:
# otherwise, we only update the ID as being seen
seenIDs.add(id)
# return result as a list
return list(result)Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
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.
