If T1 is a balanced tree with 50 million nodes, where the value of
each node is 42, and T2 is a tree with 500 nodes with all values equal
42 except the rightmost node which is 43, these approaches will take a
very long time. Any ideas on how to improve performance in such cases?
Don
On Oct 25, 3:09 am, vikas <vikas.rastogi2...@gmail.com> wrote:
> How about this
>
> Stack<tree*> st;
>
> CheckSubtree(tree *bigTree, tree *smallTree)
> {
> if(bigTree == NULL) return;
> if(bigTree->data == smallTree->data) st.Push(bigTree);
> CheckSubtree(bigTree->left, smallTree);
> CheckSubtree(bigTree->right, smallTree)
>
> }
>
> bool compareSubtrees(tree* t1, tree* t2)
> {
> if(t1 == t2) return true;
> if(t1->data != t2->data) return false;
> return compareSubtrees(t1->left, t2->left)
> && compareSubtrees(t1->right, t2->right);
>
> }
>
> Vector<bool> checkSubtreeMain(tree* big, tree* small)
> {
> CheckSubtree(tree *bigTree, tree *smallTree);
> tree *node;
> vector<bool> retValues;
> while((node = st.Pop()) != null)
> {
> bool ret = compareSubtrees(node, small);
> if(ret) retValues.push(ret);
> }
>
> printf(" subtree present @ "+retValues.size());
> return retValues;
>
>
>
>
>
>
>
> }
> On Wednesday, 24 October 2012 11:16:01 UTC+5:30, rahul sharma wrote:
>
> > 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
>
> > any other method??
> > we can also do by folloowing
>
> > 1. t1 null
> > false
> > 2. if t2 null
> > treu
> > 3. if data of both are equal call for identical fxn
>
> > just rough idea
>
> > anyother approach?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
