Related: Google – Find Duplicated Subtrees
Check if a Binary Tree contains duplicate subtrees of size 2 or more - GeeksforGeeks
Given a Binary Tree, check whether the Binary tree contains a duplicate sub-tree of size 2 or more.
Note : Two same leaf nodes are not considered as subtree size of a leaf node is one.
An Efficient solution based on tree serialization and hashing. The idea is to serialize subtrees as strings and store the strings in hash table. Once we find a serialized tree (which is not a leaf) already existing in hash-table, we return true.
A simple solution is that, we pick every node of tree and try to find is any sub-tree of given tree is present in tree which is identical with that sub-tree. Here we can use below post to find if a subtree is present anywhere else in tree.
https://gist.github.com/SahilKadam/fc9c87d7f71d1495ea90c07e2ca3dcf9
https://discuss.leetcode.com/topic/19/find-duplicate-subtrees
http://ayushcshah.github.io/algorithm/binarytree/2016/04/01/detect-duplicate-subtrees.html
Read full article from Check if a Binary Tree contains duplicate subtrees of size 2 or more - GeeksforGeeks
Check if a Binary Tree contains duplicate subtrees of size 2 or more - GeeksforGeeks
Given a Binary Tree, check whether the Binary tree contains a duplicate sub-tree of size 2 or more.
Note : Two same leaf nodes are not considered as subtree size of a leaf node is one.
An Efficient solution based on tree serialization and hashing. The idea is to serialize subtrees as strings and store the strings in hash table. Once we find a serialized tree (which is not a leaf) already existing in hash-table, we return true.
string dupSubUtil(Node *root){ string s = ""; // If current node is NULL, return marker if (root == NULL) return s + MARKER; // If left subtree has a duplicate subtree. string lStr = dupSubUtil(root->left); if (lStr.compare(s) == 0) return s; // Do same for right subtree string rStr = dupSubUtil(root->right); if (rStr.compare(s) == 0) return s; // Serialize current subtree s = s + root->key + lStr + rStr; // If current subtree already exists in hash // table. [Note that size of a serialized tree // with single node is 3 as it has two marker // nodes. if (s.length() > 3 && subtrees.find(s) != subtrees.end()) return ""; subtrees.insert(s); return s;} string str = dupSubUtil(root); (str.compare("") == 0) ? cout << " Yes ": cout << " No " ;https://gist.github.com/SahilKadam/fc9c87d7f71d1495ea90c07e2ca3dcf9
https://discuss.leetcode.com/topic/19/find-duplicate-subtrees
http://ayushcshah.github.io/algorithm/binarytree/2016/04/01/detect-duplicate-subtrees.html
A simple solution is that, we pick every node of tree and try to find is any sub-tree of given tree is present in tree which is identical with that sub-tree. Here we can use below post to find if a subtree is present anywhere else in tree.
Check if a binary tree is subtree of another binary tree
Check if a binary tree is subtree of another binary tree
The idea is based on the fact that inorder and preorder/postorder uniquely identify a binary tree. Tree S is a subtree of T if both inorder and preorder traversals of S arew substrings of inorder and preorder traversals of T respectively.
Following are detailed steps.
1) Find inorder and preorder traversals of T, store them in two auxiliary arrays inT[] and preT[].
2) Find inorder and preorder traversals of S, store them in two auxiliary arrays inS[] and preS[].
3) If inS[] is a subarray of inT[] and preS[] is a subarray preT[], then S is a subtree of T. Else not.
The above algorithm doesn't work for cases where a tree is present
in another tree, but not as a subtree. Consider the following example.
Tree1
x
/ \
a b
/
c
Tree2
x
/ \
a b
/ \
c d
Inorder and Preorder traversals of the big tree or Tree2 are.
Inorder and Preorder traversals of small tree or Tree1 are
The Tree2 is not a subtree of Tree1, but inS[] and preS[] are
subarrays of inT[] and preT[] respectively.
The above algorithm can be extended to handle such cases by adding a special character whenever we encounter NULL in inorder and preorder traversals. Thanks to Shivam Goel for suggesting this extension.
class Passing { int i; int m = 0; int n = 0;}class BinaryTree { static Node root; Passing p = new Passing(); String strstr(String haystack, String needle) { if (haystack == null || needle == null) { return null; } int hLength = haystack.length(); int nLength = needle.length(); if (hLength < nLength) { return null; } if (nLength == 0) { return haystack; } for (int i = 0; i <= hLength - nLength; i++) { if (haystack.charAt(i) == needle.charAt(0)) { int j = 0; for (; j < nLength; j++) { if (haystack.charAt(i + j) != needle.charAt(j)) { break; } } if (j == nLength) { return haystack.substring(i); } } } return null; } // A utility function to store inorder traversal of tree rooted // with root in an array arr[]. Note that i is passed as reference void storeInorder(Node node, char arr[], Passing i) { if (node == null) { arr[i.i++] = '$'; return; } storeInorder(node.left, arr, i); arr[i.i++] = node.data; storeInorder(node.right, arr, i); } // A utility function to store preorder traversal of tree rooted // with root in an array arr[]. Note that i is passed as reference void storePreOrder(Node node, char arr[], Passing i) { if (node == null) { arr[i.i++] = '$'; return; } arr[i.i++] = node.data; storePreOrder(node.left, arr, i); storePreOrder(node.right, arr, i); } /* This function returns true if S is a subtree of T, otherwise false */ boolean isSubtree(Node T, Node S) { /* base cases */ if (S == null) { return true; } if (T == null) { return false; } // Store Inorder traversals of T and S in inT[0..m-1] // and inS[0..n-1] respectively char inT[] = new char[100]; String op1 = String.valueOf(inT); char inS[] = new char[100]; String op2 = String.valueOf(inS); storeInorder(T, inT, p); storeInorder(S, inS, p); inT[p.m] = '\0'; inS[p.m] = '\0'; // If inS[] is not a substring of preS[], return false if (strstr(op1, op2) != null) { return false; } // Store Preorder traversals of T and S in inT[0..m-1] // and inS[0..n-1] respectively p.m = 0; p.n = 0; char preT[] = new char[100]; char preS[] = new char[100]; String op3 = String.valueOf(preT); String op4 = String.valueOf(preS); storePreOrder(T, preT, p); storePreOrder(S, preS, p); preT[p.m] = '\0'; preS[p.n] = '\0'; // If inS[] is not a substring of preS[], return false // Else return true return (strstr(op3, op4) != null); }
Time Complexity: Time worst case complexity of above solution is O(mn) where m and n are number of nodes in given two trees.
/* A utility function to check whether trees with roots as root1 and root2 are identical or not */ boolean areIdentical(Node root1, Node root2) { /* base cases */ if (root1 == null && root2 == null) return true; if (root1 == null || root2 == null) return false; /* Check if the data of both roots is same and data of left and right subtrees are also same */ return (root1.data == root2.data && areIdentical(root1.left, root2.left) && areIdentical(root1.right, root2.right)); } /* This function returns true if S is a subtree of T, otherwise false */ boolean isSubtree(Node T, Node S) { /* base cases */ if (S == null) return true; if (T == null) return false; /* Check the tree with root as current node */ if (areIdentical(T, S)) return true; /* If the tree with root as current node doesn't match then try left and right subtrees one by one */ return isSubtree(T.left, S) || isSubtree(T.right, S); }Read full article from Check if a Binary Tree contains duplicate subtrees of size 2 or more - GeeksforGeeks
