one optimization could be:
Inorder(big).subString(inorder(small)) == true , then only execute this
logic.
On Friday, 26 October 2012 02:54:14 UTC+5:30, Don wrote:
>
> 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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/h4OHM1bYXdIJ.
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.
