WAP to Check One Tree is SubTree of Another Tree

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

The treeMatch procedure visits each node in the small tree at most once and is called no more than once per node of the large tree. Worst case runtime is at most O(n * m), where n and m are the sizes of trees T1 and T2, respectively. If k is the number of occurrences of T2’s root in T1, the worst case runtime can be characterized as O(n + k * m).

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Given two trees, return true if they are
structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
/* If Any one Tree is Empty This can be omitted as it is covered else part */
//if(t1==NULL|| t2==NULL)
// return 0;

/*1. both empty */
if (a==NULL && b==NULL)
return 1;

/* 2. both non-empty -> compare them */
else if (a!=NULL && b!=NULL)
{
return
(
a->data == b->data &&
identicalTrees(a->left, b->left) &&
identicalTrees(a->right, b->right)
);
}
/* 3. one empty, one not -> false */
else return 0;
}



int subTree(struct node* a, struct node* b)
{
if(a==NULL)
return false;
if(b==NULL)
return true;

if(a->data==b->data)
return identicalTrees(a,b);
return (subTree(a->left,b)|| subTree(a->right,b));
}

/* Driver program to test identicalTrees function*/
int main()
{
struct node *root1 = newNode(1);
struct node *root2 = newNode(5);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root1->left->left->left = newNode(6);
root1->left->right->left = newNode(7);
root1->left->right->right = newNode(8);
root1->left->right->right->left = newNode(9);
root1->left->right->right->right = newNode(10);



root2->left = newNode(7);
root2->right = newNode(8);
root2->right->left = newNode(9);
root2->right->right = newNode(10); //to Test Diff it Try Diff Test cases

if(subTree(root1, root2))
printf("T2 is SubTree of T1");
else
printf("t2 is not SubTree of T1");

getchar();
return 0;
}

TC O(n^2)
SC O(1)
Run Here https://ideone.com/S0xWf


2nd Method to Solve It using Suffix Tree & Tree Traversal

What if We have huge Data how we can optimize it . whats the efficient way to solve it..here we go .Note that the problem here specifies that T1 has millions of nodes—this means that we should be careful of how much space we use. Let’s say, for example, T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring
of T1. We can check this using a suffix tree. However, we may hit memory limitations because suffix trees are extremely memory intensive. If this become an issue, we can use an alternative approach.

so Now problem reduce to sub-string matching isn't it..??

Using Tree Traversal
TC O(n^2)
Sc O(1)

using KMP String Search
TC O(m+n)
SC (1)

Using Suffix Tree
TC O(m) m is length of substring
Sc O(1)


To Build Suffix tree Check My Post in Blog
http://shashank7s.blogspot.com/2011/03/wap-for-given-string-s-and-array-of.html
http://www.allisons.org/ll/AlgDS/Tree/Suffix/