Check if a binary tree is subtree of another binary tree | Set 2 - GeeksforGeeks
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.
We can also use postorder traversal in place of preorder in the above algorithm.
Traverse the tree T in preorder fashion. For every visited node in the traversal, see if the subtree rooted with this node is identical to S.
Read full article from Check if a binary tree is subtree of another binary tree | Set 2 - GeeksforGeeks
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.
We can also use postorder traversal in place of preorder in the above algorithm.
The above algorithm doesn't work for cases where a tree is present in another tree, but not as a subtree.The above algorithm can be extended to handle such cases by adding a special character whenever we encounter NULL in inorder and preorder traversals.
Time Complexity: Inorder and Preorder traversals of Binary Tree take O(n) time. The function strstr()can also be implemented in O(n) time using KMP string matching algorithm.
Auxiliary Space: O(n)
Check more from http://massivealgorithms.blogspot.com/2014/07/check-if-binary-tree-is-subtree-of.html
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/class Node { char data; Node left, right; Node(char item) { data = item; left = right = null; }}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); }}Traverse the tree T in preorder fashion. For every visited node in the traversal, see if the subtree rooted with this node is identical to S.
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); }