[algogeeks] Re: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

2012-10-28 Thread vikas 
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 
  
  Stacktree* 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); 
  
  } 
  
  Vectorbool checkSubtreeMain(tree* big, tree* small) 
  { 
  CheckSubtree(tree *bigTree, tree *smallTree); 
  tree *node; 
  vectorbool 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.

[algogeeks] Re: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

2012-10-25 Thread Don 
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

 Stacktree* 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);

 }

 Vectorbool checkSubtreeMain(tree* big, tree* small)
 {
     CheckSubtree(tree *bigTree, tree *smallTree);
     tree *node;
     vectorbool 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.