Google Interview Question
Software EngineersCountry: United States
I don't believe the assumptions you make about levels are valid. In the following example, your solution will fail:
M
/ \
A A
|\ |\
E F E G
| |
B B
|\ |\
C D C D
inorder: E A C B D F M E A C B D G
levels: 3 2 5 4 5 3 1 3 2 5 4 5 3
Pair: {ACBD, 2545}
According to your algorithm, this would return true... however, ACBD is not a subtree.
sorry, but your in-order traversal is wrong. Depending on direction of edges it should start either ECBDA... or CBDEA...
Also, from your picture it is obvious that the end of in-order traversal must be ...MEAG.
But you wrote something different.
So, I can say nothing definite about your conclusion, 'cause it is based on wrong idea.
Can you specify the tree more accurately, in such notation:
M( A ( E ( <left>, <right> ), F ( <left>, <right> ) ), A ( E, G ) )
sorry, looks like you are totally wrong.
I examined all the possible trees, which can be made up from your picture.
They are (in-order traversals):
1) ECBDACBDFMEAG
2) ECBDAFCBDMEAG
3) CBDEACBDFMEAG
4) CBDEAFCBDMEAG
My solution works greatly on all these variants. The answer is true, because the result pair is {CBD, 434}.
thanks, this is a great observation.
really, my solution does not handle this situation.
A small improvement is needed: when we receive 2 identical nodes sequence, then we must check if the respective levels sequence can be reduced one to another via iterative subtracting 1 from each digit of a respective seq.
Example:
{ABC, 212} and {ABC, 021} - the answer is no, because we cannot reduce 212 to 021 (and vice versa).
{ECF, 323} and {ECF, 212} - the answer is yes (the tree has duplicate sub trees), because we can reduce 323 to 212 via iterative subtracting 1 from each digit in first number (323). So, here we need 1 iteration.
Thanks again, you helped to improve the solution.
How do you find common substring(longest may be) in single string. In your example1 inorder is ABCDABC.
What algorithm to use to find, substring in same same string. I am aware of DP solution for different strings.
this can be done using hashtable. There may be variations in implementation, but general idea is as follows:
let's have ABCDABC in-order traversal result.
So, we start from position 0 and put all letters one by one into hashtable:
1) {'A', 0}
2) {'B', 1}
3) {'C', 2}
4) {'D', 3}
Then when we'll try to put {'A', 4}, we'll get an exception. This is the signal that we found duplication. So, starting from positions 0 and 4 we obtain duplicate parts and do all the necessary checks (described in solution). If the checks are passed we are done. Otherwise we proceed putting into hashtable remaining characters.
Certainly, this is much faster than O(n^2), but maybe a little slower than O(n). Actually, this is order O(n) or at most O(n logn).
to find two identical substrings of a string one can build a suffix tree.
If zr.roman elaborated his solution with hashtable it would be nice.
This algo works with the correction in one of the comments.
If the question is to find if there are such subtrees of a given length L (yes/no) or just if there are subtrees (which is equivalent to subtrees of a given length 2) , it's possible to implement this in O(N). If the question is to find all such subtrees (any possibl length), it becomes O(N^3).
public void checkIfDupSubTrees(ArrayList<TreeNode> dump, ArrayList<TreeNode> ans)
{
for(int i=0; i<dump.size()-1; i++)
{
for (int j=i+1; j<dump.size(); j++)
{
TreeNode check = checkEqualTrees(dump.get(i), dump.get(j));
if (check!=null && (check.getLeft()!=null || check.getRight()!=null))
ans.add(check);
}
}
ArrayList<TreeNode> newDump = new ArrayList<TreeNode>();
for(int i=0; i<dump.size(); i++)
{
TreeNode left = dump.get(i).getLeft();
TreeNode right = dump.get(i).getRight();
if (left!=null)
newDump.add(left);
if (right!=null)
newDump.add(right);
}
if (newDump.size()>=1)
checkIfDupSubTrees(newDump, ans);
}
private TreeNode checkEqualTrees(TreeNode one, TreeNode two)
{
if (one.getVal()!=two.getVal())
return null;
else
{
TreeNode ans = new TreeNode(one.getVal());
if (one.getLeft()!=null && two.getLeft()!=null)
ans.setLeft(checkEqualTrees(one.getLeft(), two.getLeft()));
else
ans.setLeft(null);
if (one.getRight()!=null && two.getRight()!=null)
ans.setLeft(checkEqualTrees(one.getRight(), two.getRight()));
else
ans.setRight(null);
return ans;
}
}
public void checkIfDupSubTrees()
{
TreeNode root = new TreeNode(3);
TreeNode one = new TreeNode(6);
TreeNode two = new TreeNode(8);
TreeNode three = new TreeNode(5);
TreeNode four = new TreeNode(5);
TreeNode five = new TreeNode(4);
TreeNode six = new TreeNode(20);
TreeNode seven = new TreeNode(20);
TreeNode eight = new TreeNode(2);
TreeNode nine = new TreeNode(25);
TreeNode ten = new TreeNode(4);
TreeNode eleven = new TreeNode(2);
TreeNode twelve = new TreeNode(9);
TreeNode thirteen = new TreeNode(11);
root.setLeft(one);
root.setRight(two);
one.setLeft(three);
two.setRight(four);
three.setLeft(five);
three.setRight(six);
five.setLeft(seven);
five.setRight(eight);
seven.setRight(nine);
four.setLeft(ten);
ten.setLeft(twelve);
ten.setRight(eleven);
twelve.setRight(thirteen);
ArrayList<TreeNode> dump = new ArrayList<TreeNode>();
ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
dump.add(root);
checkIfDupSubTrees(dump, ans);
System.out.println("CheckIfDupSubTrees===========================");
System.out.println("Root Tree===========================");
printTree(root);
System.out.println("===========================");
for(int i=0; i<ans.size();i++)
{
System.out.println("DupSubTrees===========================");
printTree(ans.get(i));
System.out.println("===========================");
}
}
public void printTree(TreeNode t)
{
System.out.print(t.getVal());
if (t.getLeft()!=null)
System.out.print("-->Left-"+t.getLeft().getVal());
if (t.getRight()!=null)
System.out.print("-->Right-"+t.getRight().getVal());
System.out.println();
if (t.getLeft()!=null)
printTree(t.getLeft());
if (t.getRight()!=null)
printTree(t.getRight());
}
a single node could be considered as a sub tree (connected with no circles), therefor, it could be achieved in O(n) :
traverse the tree (in-order, post-order..doesn't really matter):
- add current node to hash_table:
- if node of the same value was already inserted: return that there is a duplicate
(after traverse is finished) return there's no duplicates
public void checkIfDupSubTrees(ArrayList<TreeNode> dump, ArrayList<TreeNode> ans)
{
for(int i=0; i<dump.size()-1; i++)
{
for (int j=i+1; j<dump.size(); j++)
{
TreeNode check = checkEqualTrees(dump.get(i), dump.get(j));
if (check!=null && (check.getLeft()!=null || check.getRight()!=null))
ans.add(check);
}
}
ArrayList<TreeNode> newDump = new ArrayList<TreeNode>();
for(int i=0; i<dump.size(); i++)
{
TreeNode left = dump.get(i).getLeft();
TreeNode right = dump.get(i).getRight();
if (left!=null)
newDump.add(left);
if (right!=null)
newDump.add(right);
}
if (newDump.size()>=1)
checkIfDupSubTrees(newDump, ans);
}
private TreeNode checkEqualTrees(TreeNode one, TreeNode two)
{
if (one.getVal()!=two.getVal())
return null;
else
{
TreeNode ans = new TreeNode(one.getVal());
if (one.getLeft()!=null && two.getLeft()!=null)
ans.setLeft(checkEqualTrees(one.getLeft(), two.getLeft()));
else
ans.setLeft(null);
if (one.getRight()!=null && two.getRight()!=null)
ans.setLeft(checkEqualTrees(one.getRight(), two.getRight()));
else
ans.setRight(null);
return ans;
}
}
public void checkIfDupSubTrees()
{
TreeNode root = new TreeNode(3);
TreeNode one = new TreeNode(6);
TreeNode two = new TreeNode(8);
TreeNode three = new TreeNode(5);
TreeNode four = new TreeNode(5);
TreeNode five = new TreeNode(4);
TreeNode six = new TreeNode(20);
TreeNode seven = new TreeNode(20);
TreeNode eight = new TreeNode(2);
TreeNode nine = new TreeNode(25);
TreeNode ten = new TreeNode(4);
TreeNode eleven = new TreeNode(2);
TreeNode twelve = new TreeNode(9);
TreeNode thirteen = new TreeNode(11);
root.setLeft(one);
root.setRight(two);
one.setLeft(three);
two.setRight(four);
three.setLeft(five);
three.setRight(six);
five.setLeft(seven);
five.setRight(eight);
seven.setRight(nine);
four.setLeft(ten);
ten.setLeft(twelve);
ten.setRight(eleven);
twelve.setRight(thirteen);
ArrayList<TreeNode> dump = new ArrayList<TreeNode>();
ArrayList<TreeNode> ans = new ArrayList<TreeNode>();
dump.add(root);
checkIfDupSubTrees(dump, ans);
System.out.println("CheckIfDupSubTrees===========================");
System.out.println("Root Tree===========================");
printTree(root);
System.out.println("===========================");
for(int i=0; i<ans.size();i++)
{
System.out.println("DupSubTrees===========================");
printTree(ans.get(i));
System.out.println("===========================");
}
}
public void printTree(TreeNode t)
{
System.out.print(t.getVal());
if (t.getLeft()!=null)
System.out.print("-->Left-"+t.getLeft().getVal());
if (t.getRight()!=null)
System.out.print("-->Right-"+t.getRight().getVal());
System.out.println();
if (t.getLeft()!=null)
printTree(t.getLeft());
if (t.getRight()!=null)
printTree(t.getRight());
}
Given T, find:
1. Let array A be the in-order traversal of T.left
2. Let array B be the in-order traversal of T.right
Both A and B can be produced in one pass - make sure to add a marker for whenever you see a null on one side but not the other - this guarantees A and B will have the same size, which will come in handy in further steps.
3. Let array C be the pre-order traversal of T.left
4. Let array D be the pre-order traversal of T.right
Likewise, both C and D can be produced in one pass - make sure to add a marker for whenever you see a null on one side but not the other - this guarantees C and D will have the same size.
5. Check if A has a sequence which is also in B (since A and B are the same size, this can be done in O(n) )
6. Check if C has a sequence which is also in D (since C and D are the same size, this can be done in O(n) )
7. If both 5 and 6 are true, continue, otherwise we can return false
8. If the sequences found in 5 and 6 are a permutation of each other (can be done in O(n)), then return true.
The duplicate sub-trees can occur along the same arm of the tree. I mean, in T.left, there's a possibility that you may find 2 duplicate subtrees. Similarly, in T.right itself, there may be duplicate sub trees.
1. Add a data field with childcount which helps in visible bit and subtree rule scheme.
2. perform post order traversal ,
3. If we encountered a node , whose value is defined and also defined as subtree ( i.e >=3) , terminate and declare it as solution.
4. Set current node child count as 1+ left + right child count.
private boolean duplicateFound = false;
private List<Node> subTreeRoots = new ArrayList<TreeBuilder.Node>();
private void traverseTree(Node node) {
if (!duplicateFound) {
if (node != null) {
//is a parent
if (node.left != null || node.right != null) {
for (Node compareNode : subTreeRoots) {
//before comparison, we could add a check to see if compareNode is it's parent, then don't compare.
duplicateFound = isIdentical(compareNode, node);
if (duplicateFound) {
System.out.println("Dup1 is " + node + " Dup2 is " + compareNode);
break;
}
}
subTreeRoots.add(node);
}
traverseTree(node.left);
traverseTree(node.right);
}
}
}
private boolean isIdentical(TreeBuilder.Node node1, TreeBuilder.Node node2) {
if (node1 == null && node2 == null) {
return true;
}
if (node1 == null || node2 == null) {
return false;
}
return node1.id.equals(node2.id)
&& isIdentical(node1.left, node2.left)
&& isIdentical(node1.right, node2.right);
}
public class Node
{
int value;
Node left;
Node right;
}
public boolean hasDupSubtrees(Node n)
{
if(n==null||(n.left==null && n.right==null))
{
return false;
}
ArrayList<Integer> ls=new ArrayList<Integer>();
return checkSubtrees(n,ls,0);
}
private boolean checkSubtrees(Node n, ArrayList<Integer> ls, int start)
{
if(n==null)
{
return false;
}
boolean left=checkSubtrees(n.left,ls,start);
boolean right=true;
if(!left)
{
int leftTreeSize=ls.size()-start;
right=checkSubtrees(n.right,ls,start+leftTreeSize);
}
if(!right)
{
int rightTreeSize=ls.size()-leftTreeSize;
if(rightTreeSize==leftTreeSize && leftTreeSize>1)
{
right=checkNodeValues(ls,start,leftTreeSize);
}
}
ls.add(n.value);
return (left||right);
}
private boolean checkNodeValues(ArrayList<Integer> ls, int start, int treeSize)
{
int leftIdx=start;
int leftEnd=start+treeSize;
int rightIdx=leftEnd;
while(leftIdx<leftEnd)
{
if(!ls.get(leftIdx).equals(ls.get(rightIdx)))
{
return false;
}
}
return true;
}
//Time: O(nlogn) Space: O(n) where n is the number of nodes in the tree.
**Forgot just 2 lines see below:
private boolean checkNodeValues(ArrayList<Integer> ls, int start, int treeSize)
{
int leftIdx=start;
int leftEnd=start+treeSize;
int rightIdx=leftEnd;
while(leftIdx<leftEnd)
{
if(!ls.get(leftIdx).equals(ls.get(rightIdx)))
{
return false;
}
leftIdx++;//Missing line 1
rightIdx++//Missing line 2
}
return true;
}
Crafted a dynamic solution and it avoids all the problem shown in the approach of in-order solution because it is to compare the tree exactly match. Details: cpluspluslearning-petert.blogspot.co.uk/2016/01/dynamic-programming-find-if-given-tree.html
Test
void TestFindDuplicateSubTree()
{
{
TreeNode<int>* root = nullptr;
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
}
{
const std::vector<int> testInput = { 1, 2 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput = { 100, 101 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root);
auto rightestNode = FindRightestNode(root);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root);
auto rightestNode = FindRightestNode(root);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root->left);
auto rightestNode = FindRightestNode(root->left);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 4);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));
DeleteTree(&root);
}
}
Crafted a linear solution (to size of tree). The idea is to calculate hash for each node that includes all the information of its sub-tree. Then compare those nodes with same hash code. Details: cpluspluslearning-petert.blogspot.co.uk/2016/01/dynamic-programming-find-if-given-tree_69.html
Test
void TestFindDuplicateSubTree2()
{
{
TreeNode<int>* root = nullptr;
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
}
{
const std::vector<int> testInput = { 1, 2 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput = { 100, 101 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root);
auto rightestNode = FindRightestNode(root);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root);
auto rightestNode = FindRightestNode(root);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root->left);
auto rightestNode = FindRightestNode(root->left);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 1);
assert(*rightestNode->data == 4);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1;
TreeNode<int>* entry2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput = { 100, 101, 102 };
auto subTree1 = ConstructTreeRecursive(subTreeInput);
auto subTree2 = ConstructTreeRecursive(subTreeInput);
assert(GetTreeSize_R(subTree1) == subTreeInput.size());
assert(GetTreeSize_R(subTree2) == subTreeInput.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == true);
assert(entry1 != nullptr);
assert(entry2 != nullptr);
assert(CheckTwoTreesWithSameValues(entry1, subTree1));
assert(CheckTwoTreesWithSameValues(entry2, subTree2));
assert(CheckTwoTreesWithSameValues(entry1, entry2));
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1 = nullptr;
TreeNode<int>* entry2 = nullptr;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
const std::vector<int> subTreeInput1 = { 100, 101, 102 };
const std::vector<int> subTreeInput2 = { 102, 101, 100 };
auto subTree1 = ConstructTreeRecursive(subTreeInput1);
auto subTree2 = ConstructTreeRecursive(subTreeInput2);
assert(GetTreeSize_R(subTree1) == subTreeInput1.size());
assert(GetTreeSize_R(subTree2) == subTreeInput2.size());
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
assert(entry1 == nullptr);
assert(entry2 == nullptr);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1 = nullptr;
TreeNode<int>* entry2 = nullptr;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
TreeNode<int>* subTree1 = new TreeNode<int>(1000);
subTree1->left = new TreeNode<int>(1001);
subTree1->left->left = new TreeNode<int>(1002);
TreeNode<int>* subTree2 = new TreeNode<int>(1000);
subTree2->right = new TreeNode<int>(1001);
subTree2->right->right = new TreeNode<int>(1002);
assert(GetTreeSize_R(subTree1) == 3);
assert(GetTreeSize_R(subTree2) == 3);
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
assert(entry1 == nullptr);
assert(entry2 == nullptr);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1 = nullptr;
TreeNode<int>* entry2 = nullptr;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
TreeNode<int>* subTree1 = new TreeNode<int>(1000);
subTree1->left = new TreeNode<int>(1001);
subTree1->right = new TreeNode<int>(1002);
TreeNode<int>* subTree2 = new TreeNode<int>(1000);
subTree2->right = new TreeNode<int>(1001);
subTree2->right->right = new TreeNode<int>(1002);
assert(GetTreeSize_R(subTree1) == 3);
assert(GetTreeSize_R(subTree2) == 3);
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
assert(entry1 == nullptr);
assert(entry2 == nullptr);
DeleteTree(&root);
}
{
const std::vector<int> testInput = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
auto root = ConstructTreeRecursive(testInput);
assert(root != nullptr);
assert(GetTreeSize_R(root) == testInput.size());
TreeNode<int>* entry1 = nullptr;
TreeNode<int>* entry2 = nullptr;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
TreeNode<int>* subTree1 = new TreeNode<int>(1000);
subTree1->right = new TreeNode<int>(1002);
subTree1->right->right = new TreeNode<int>(1001);
TreeNode<int>* subTree2 = new TreeNode<int>(1000);
subTree2->right = new TreeNode<int>(1001);
subTree2->right->right = new TreeNode<int>(1002);
assert(GetTreeSize_R(subTree1) == 3);
assert(GetTreeSize_R(subTree2) == 3);
assert(CheckTwoTreesWithSameValues(subTree1, subTree2) == true);
auto leftestNode = FindLeftestNode(root->right);
auto rightestNode = FindRightestNode(root->right);
assert(leftestNode != nullptr);
assert(leftestNode->left == nullptr);
assert(rightestNode != nullptr);
assert(rightestNode->right == nullptr);
assert(*leftestNode->data == 6);
assert(*rightestNode->data == 10);
leftestNode->left = subTree1;
rightestNode->right = subTree2;
assert(HaveDuplicateSubTree2_R(root, entry1, entry2) == false);
assert(entry1 == nullptr);
assert(entry2 == nullptr);
DeleteTree(&root);
}
}
If a single node can be considered as a subtree the solution is trivial - just check duplicated leaf nodes. If the "subtree" should have at least 2 nodes, then we are ok to check all the triplets of "node, left child, right child" when both left and right children are either leafs or missing (but not both missing). Here's some code:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def isleaf(node):
if node is None:
return True
else:
if node.left is None and node.right is None:
return True
return False
def get_triplets(node):
res = []
if node.left is None:
res.append(None)
else:
res.append(node.left.value)
res.append(node.value)
if node.right is None:
res.append(None)
else:
res.append(node.right.value)
return ['|'.join([str(x) for x in res]), '|'.join([str(x) for x in res[::-1]])]
def find_triplets(node):
if node is None or isleaf(node):
return []
if isleaf(node.left) and isleaf(node.right):
return get_triplet(node)
return find_triplets(node.left) + find_triplets(node.right)
def hasdup(node):
unique = set()
for tr in find_triplets(node):
if tr in unique:
return True
unique.add(tr)
return False
a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
a.left = b
a.right = c
d = TreeNode(1)
e = TreeNode(2)
f = TreeNode(5)
d.left = f
d.right = e
g = TreeNode(0)
g.left = a
g.right = d
print hasdup(g)
Any two duplicate subtrees have at least 3 nodes in common - root, left and right. In order to answer this question it is enough to find 2 subtrees having those 3 nodes equal.
Construct a hash multimap. Every new node goes into the map. If same value already exists, check if left=left and right=right. Stop if found. That's all.
Hi, my answer is quite simple:
A. go in-order traversal, and add each node to a Map<NodeValue, Node>
B. During in-order tranversal, if I find a already stored value, then I start to check if both are equal.
public class FindDuplicatedSubTrees {
private Map<Integer, List<TreeNode>> nodes;
/**
* @param args
*/
public static void main(String[] args) {
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.left.right = new TreeNode(11);
root.left.left = new TreeNode(20);
root.left.left.left = new TreeNode(5);
root.left.left.right = new TreeNode(6);
root.right = new TreeNode(6);
root.right.left = new TreeNode(9);
root.right.right = new TreeNode(8);
root.right.right.left = new TreeNode(5);
root.right.right.left.right = new TreeNode(11);
root.right.right.left.left = new TreeNode(20);
root.right.right.left.left.left = new TreeNode(5);
root.right.right.left.left.right = new TreeNode(6);
System.out.println(new FindDuplicatedSubTrees().hasDuplicatedSubTrees(root));
}
public boolean hasDuplicatedSubTrees(TreeNode root) {
if (nodes == null) {
nodes = new HashMap<Integer, List<TreeNode>>();
}
if(root == null) {
return false;
}
if (root.left == null && root.right == null) {
return false;
}
if (!nodes.containsKey(root.data)) {
List<TreeNode> ns = new ArrayList<FindDuplicatedSubTrees.TreeNode>();
ns.add(root);
nodes.put(root.data, ns);
}
else {
List<TreeNode> ns = nodes.get(root.data);
for (TreeNode treeNode : ns) {
if (equals(treeNode, root, treeNode, root)) {
return true;
}
}
}
if (hasDuplicatedSubTrees(root.left)) {
return true;
}
return hasDuplicatedSubTrees(root.right);
}
private boolean equals(TreeNode na, TreeNode nb, TreeNode roota, TreeNode rootb) {
if (na == rootb || nb == roota) {
return false;
}
if (na != null && nb == null || na == null && nb != null) {
return false;
}
if (na == null && nb == null) {
return true;
}
if (na.data == nb.data) {
if (equals(na.left, nb.left, roota, rootb)) {
return equals(na.right, nb.right, roota, rootb);
}
}
return false;
}
private static class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
super();
this.data = data;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return data + "";
}
}
}
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def detect_dup_sub(tree, tree_sets=set()):
if tree is None:
return False, tuple()
left_res, left_tree = detect_dup_sub(tree.left, tree_sets)
right_res, right_tree = detect_dup_sub(tree.right, tree_sets)
if left_res or right_res:
return True, tuple()
this_tree = left_tree + (tree.value,) + right_tree
# this_tree is a inorder list of the subtree
if len(this_tree) > 3 and this_tree in tree_sets:
return True, tuple()
else:
tree_sets.add(this_tree)
return False, this_tree
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def detect_dup_sub(tree, tree_sets=set()):
if tree is None:
return False, tuple()
left_res, left_tree = detect_dup_sub(tree.left, tree_sets)
right_res, right_tree = detect_dup_sub(tree.right, tree_sets)
if left_res or right_res:
return True, tuple()
this_tree = left_tree + (tree.value,) + right_tree
# this_tree is a inorder list of the subtree
if len(this_tree) > 3 and this_tree in tree_sets:
return True, tuple()
else:
tree_sets.add(this_tree)
return False, this_tree
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def detect_dup_sub(tree, tree_sets=set()):
if tree is None:
return False, tuple()
left_res, left_tree = detect_dup_sub(tree.left, tree_sets)
right_res, right_tree = detect_dup_sub(tree.right, tree_sets)
if left_res or right_res:
return True, tuple()
this_tree = left_tree + (tree.value,) + right_tree
# this_tree is a inorder list of the subtree
if len(this_tree) > 3 and this_tree in tree_sets:
return True, tuple()
else:
tree_sets.add(this_tree)
return False, this_tree
struct Node {
Node * left, *right;
Node() : left{ nullptr }, right{ nullptr } {}
};
string detect_duplicate_subtrees_helper(
Node * tree,
unordered_map<string, int> & storage
) {
if (tree == nullptr) {
return "";
}
else {
string l = detect_duplicate_subtrees_helper(tree->left, storage);
string r = detect_duplicate_subtrees_helper(tree->right, storage);
if (r < l) swap(l, r);
const string code = "0" + l + "10" + r + "1";
storage[code]++;
return code;
}
}
void detect_duplicate_subtrees(Node * tree) {
unordered_map<string, int> storage;
detect_duplicate_subtrees_helper(tree, storage);
for (auto & a : storage) {
if (a.second > 0) {
cout << a.first << " " << a.second << endl;
}
}
}
int main()
{
/*
root
/ \
a b
\ /
c d
\ \
e f
*/
Node root, a, b, c, d, e, f;
root.left = &a;
root.right = &b;
a.right = &c;
c.right = &e;
b.left = &d;
d.right = &f;
detect_duplicate_subtrees(&root);
return 0;
}
public static boolean isContainsDuplicateTrees(TreeNode root) {
return isContainsDuplicateTrees(new TreeSet<>(), root);
}
public static boolean isContainsDuplicateTrees(Set<String> trees, TreeNode root) {
if (root != null) {
String tree = "";
if (root.leftNode != null) {
tree += root.leftNode.nodeName;
}
tree += root.nodeName;
if (root.rightNode != null) {
tree += root.rightNode.nodeName;
}
if (trees.contains(tree)) {
System.out.println(tree);
return true;
}
if (tree.length() == 3) {
System.out.println(tree);
trees.add(tree);
}
boolean isLeftHave = false;
if (root.leftNode != null) {
isLeftHave = isContainsDuplicateTrees(trees, root.leftNode);
}
boolean isRightHave = false;
if (root.rightNode != null) {
isRightHave = isContainsDuplicateTrees(trees, root.rightNode);
}
return (isLeftHave || isRightHave);
}
return false;
}
class TreeNode:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
subtrees = set()
def subDup(root):
if root == None:
return False, ""
lstr = ""
rstr = ""
xl = False
xr = False
if root.left:
(xl, lstr) = subDup(root.left)
if root.right:
(xr, rstr) = subDup(root.right)
if xl or xr:
return True, ""
s = root.value + lstr + rstr
if len(s) > 2 and s in subtrees:
return True, s
subtrees.add(s)
return False, s
root = TreeNode("A")
root.left = TreeNode("B")
root.left.left = TreeNode("E")
root.left.right = TreeNode("E")
root.right = TreeNode("C")
root.right.left = TreeNode("B")
root.right.left.left = TreeNode("E")
root.right.left.right = TreeNode("E")
print(subDup(root)[0])
no, it's not that simple,
consider the example:
A
/ \
B C
/ \ \ \
AC B D
In-order traversal: ABCABCD.
Longest repeating seq is ABC, but there are no duplicate sub trees in the tree.
the solution is to perform in-order traversal, and obtain 2 sequences:
- zr.roman December 29, 2015seq of nodes and seq of levels.
Then find duplicate sub sequences while comparing the corresponding sub sequences of levels and additionally checking the proper begin and end of sub sequence (explained in examples 3 and 4).
If we find a pair: 2 identical subseqs of nodes and 2 identical subseqs of levels then the answer is true (i.e. tree has sub trees).
Example 1:
D
| \
B B
| \ \ \
A C A C
In-order traversal result:
ABCDABC
212 0 212
We have 2 identical pairs: {ABC, 212} and {ABC, 212}, so the tree has duplicate sub trees.
Example 2:
A
| \
B C
| \ \ \
A C B D
In-order traversal result:
ABCABCD
212 021 2
Though we have 2 duplicate nodes subseqs: ABC and ABC, but the corresponding levels subseqs are not identical: 212 and 021. So there are no duplicate sub trees in the tree.
Example 3:
D
| \
B B
| \ \
A C A
In-order traversal result:
ABCDAB
212 0 21
We have 2 identical pairs: {AB, 21} and {AB, 21}, but additional check fails. First AB is not a valid subseq because the next level after 21 is 2, this means that the sub tree has one more node ('cause 2 > 1), that is why the first pair should be {ABC, 212}.
So, {ABC, 212} and {AB, 21} are not identical, so again there are no duplicate sub trees in the tree.
Example 4:
D
| \
B B
\ \ \
C A C
In-order traversal result:
BCDABC
12 0 212
We have 2 identical pairs: {BC, 12} and {BC, 12}, but additional check fails. Second BC is not a valid subseq because the prev level before 1 is 2, this means that the sub tree has one more node ('cause 2 > 1), that is why the second pair should be {ABC, 212}.
So, {BC, 12} and {ABC, 212} are not identical, so again there are no duplicate sub trees in the tree.