Google Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
3
of 3 vote

the solution is to perform in-order traversal, and obtain 2 sequences:
seq 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.

- zr.roman December 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- lima.gus December 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ) )

- zr.roman December 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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}.

- zr.roman December 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

@zr.roman, what will be the answer for

B
/ \
A C
/ \ / \
C D E F
/ \
E F

- Hasit Bhatt January 02, 2016 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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.

- zr.roman January 02, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- prodigy January 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- zr.roman January 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Yola January 23, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- Alex M. May 25, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

If two subtrees of length h are equal then two subtrees of length h-1 are also equal.

So just need to check if there exists duplicate edges using hash function. Problem stmt is not clear but whatever is stmt is given I can write mentioned solution.

- Anonymous December 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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());
	}

- monika December 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

So, is it O(n^3) of what? Anyway would be nice to have very succinct description of the algorithm.

- Yola January 23, 2016 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- chuck norris January 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here we need to have hashCode implemented for the Node, which in worse case scenario needs to go through every node (for the tree root), which is O(n), hence final complexity would be O(n^2)

- Bartek March 03, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Mistake

- EPavlova December 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about finding sequences of 3 nodes (head, left, right) as duplicates in the tree? Would have a lognlogn complexity.

- erik December 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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());
	}

- monika December 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- lima.gus December 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- kaukabhishek January 12, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you solve #6 in o(n) ?
"6. 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) )"

- prodigy January 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- ankushbindlish December 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

a single node could be considered as a sub-tree(connected and non-cyclic graph)
O(n) one traverse, use a hash table to insert the nodes to, and check if the current node was previously added, if so then return true. after the traverse finish, means there's no duplicates

- chuckNorris January 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Prepare hashmap of node value and list of tree node (Map<String,List<TreeNode>>) while doing pre-order traversal
2.Get List<TreeNode> from map where List size is greater then 2
3.call recursive tree match method on the TreeNodes from the list.

- Anonymous January 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }

- SK January 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- divm01986 January 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

**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;
	}

- divm01986 January 17, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
}

- peter tang January 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
    }
}

- peter tang January 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- 0x0FFF January 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- alkatzo February 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 + "";
}

}

}

- Antonio February 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- use hash set to keep track of subtree seen so far March 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- use hash set to keep track of subtree seen so far March 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- lukas.mach April 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- dhiralpandya May 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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])

- snugkim April 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

find longest repeating seq over inorder traversal string for the tree.

- gzam December 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zr.roman December 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Instead of A, B, C,.., what about LRV sequence? Then gzam's solution works fine.

- Anonymous January 09, 2016 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More