Mustafa S
Duplicate subtrees check
The problem here is that, given the root of binary tree, check if it's unique. Unique trees are defined as trees that don't have any two subtrees with the same structure, the same values, and the same ordering of the values. Leaves nodes should not be considered (i.e. two leaves with the same values are not duplicates).
Lets go through an examples and their correct output.
1 | 1 | 1
/ \ | / \ | / \
2 4 | 2 3 | 2 2
/ \ / \ | / \ / \ |
2 4 4 2 | 4 5 6 7 |
/ \ | |
2 4 | |
| |
output: false | output: true | return: true
In the first example, the output is false because there exists a subtree that have the same values, structure, and ordering. The following subtree appears twice.
2
/ \
2 4
Once in the left side of the tree, and once in the bottom right of the tree.
Solution
The idea of the solution is very similar to the solution of checking if an array contains duplicate values. In that solution, we simply iterate through the array and add the value to a hashset, and if the value already exists, we return false. If reach the end of the list and we added all values to the hashset, we return true. The problem statements is somewhat the same; check if the subtree has duplicates. The difference is in the array problem, we actually know what to store in the hashset, which is simply the value of array at the index we are currently at. Here, we can not just store the value of the node because each node might have different children or different structures. Instead, what we could do is represent the node in a string that will hold the structure information, as well as the values and how they're ordered in the tree.
Let's see how can we represent the node in a string. This is the same as asking you to serialize a binary tree. Some tree serialization methods will return the level order of the tree (i.e. it will return a string that represents the tree level by level). This is correct, and would also work, but since we are going to iterate through the whole tree, we should take advantage of nodes that we already 'serialized' (i.e. already computed it's string representation) previously so that we don't need to serialize again. This is where dynamic programming would be useful. We should memoize the string representation of a node, so that when we need to serialize the parent, we will use the memoized children values to serialize it. Let's go through an example
2 | 2 | 2 | 2
| 4 | 4 | 3 4
| | |
2 ## '2 | 2 # & 4 ## '4 '2 | 2 4 ## '4 & # '2| 2 3 ## '3 & 4 ## '4 '2
Take a few minutes to analyze the representation. Note that you can do whatever representation you feel is best, as long as it saves the structure and the ordering of the values. The one I wrote here is the one I felt easier to understand and visualize.
In the first example, a leaf node, we start by putting the value of the root and root prime, and whatever is between these two are the representation of the node's children. In this case, it's a leaf, so we add ## as a way of saying that this node has null for its left child and null for its right child.
In the second example, This node has a right child only. Similarly add the root and root prime, and whatever is in between should represent the children of the node. In this case the left child is null, so we add a single # and then we add a & to separate the left child from the right (note: this is not really needed but added for easier understanding) then we add the string representation of it's right child.
In the third example, it's the same as the second but we switched the values of the left and right children. In the final example, we just add the representation of the left child, separate by an & and the string representation of the right child.
Now that we have a way to represent the nodes, we just iterate through the tree in post-order way (because we want to get the representation of the children first before doing the parent) and add them to a hashmap. We use the hashmap for memoization. We also add a hashset of the string representation. Whenever we encounter a node that is not a leaf (because of the problem statement) we add it to the hashset. If it already exist, it means that another subtree with the same structure and ordering of values exists, therefore we return false. If we are done iterating, we return true.
public static boolean isUniqueResult = true; // global var
public static void isUnique(TreeNode root, HashMap<TreeNode, String> dp, HashSet<String> values){
if(root == null) return;
// post-order
isUnique(root.left, dp, values);
isUnique(root.right, dp, values);
String v = Integer.toString(root.val);
String rep; // node representation
if(isLeaf(root))
rep = v + " ## '" + v;
else if(root.left != null && root.right == null)
rep = v + " " + dp.get(root.left) + " | # '" + v;
else if(root.left == null && root.right != null)
rep = v + " # | " + dp.get(root.right) + " '" + v;
else
rep = v + " " + dp.get(root.left) + " | " + dp.get(root.right) + " '" + v;
if(values.contains(rep))
isUniqueResult = false;
if(!isLeaf(root))
values.add(rep);
dp.put(root, rep);
}
public static boolean isLeaf(TreeNode root){
return root.left == null && root.right == null;
}
public static void main(String[] args){
/***
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
*/
TreeNode root = new TreeNode(6);
TreeNode two = new TreeNode(2);
TreeNode zero = new TreeNode(0);
TreeNode four = new TreeNode(4);
TreeNode three = new TreeNode(3);
TreeNode five = new TreeNode(5);
TreeNode eight = new TreeNode(8);
TreeNode seven = new TreeNode(7);
TreeNode nine = new TreeNode(9);
root.left = two;
root.right = eight;
two.left = zero;
two.right = four;
four.left = three;
four.right = five;
eight.left = seven;
eight.right = nine;
HashMap<TreeNode, String> dp = new HashMap<>();
HashSet<String> values = new HashSet<>();
isUnique(root, dp, values);
System.out.println(isUniqueResult);
}
Thanks for reading! and let me know if you have any feedback.