Re: [algogeeks] Re: Merging of Binary trees

2010-07-27 Thread Ashish Goel 
i donot think that the link provided is for the same problem, the link
provides a solution to balance a tree whereas this problem is to merge
two BST without any limitation on the balance factor

having said that th balancing the tree itself is an interesting
problem and i must say that the documentation is poor here.. (:

On 7/27/10, Gene gene.ress...@gmail.com wrote:
 You actually only need a singly linked list.  See and old discussion
 about this at

 http://groups.google.com/group/comp.programming/msg/41f46b2801c4f84e

 This will do the job in O(n).

 On Jul 26, 11:00 pm, Ashish Goel ashg...@gmail.com wrote:
 Jalaj,

 How do you convert a Circular DLL to BST??
 Please refer my solution, and coorect it if needed;)

 Regards
 Ashish

 On 7/26/10, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:





  suppose both trees contains n nodes
  then converting to dll both the trees O(n) + O(n)
  then merging two dll's O(n)
  converting back to tree also O(2*n)=O(n)..// not sure about it

  code for converting tree to dll
  node * bsttolist(node *root){
if(root==NULL) return NULL;
node *l=bsttolist(root-left);
node *r=bsttolist(root-right);
root-left=root;
root-right=root;
append(l,root);
append(l,r);
return l;
  }

  here append function merges two circular doubly linked lists , you can
  make
  that on your own

  On Mon, Jul 26, 2010 at 5:52 PM, Manjunath Manohar
  manjunath.n...@gmail.com
  wrote:

  @jalaj: could u pls elaborate on that a bit more..will it have the
  complexity of O(n logn logn), and also can u provide the pseudocode
  pls..

  --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To post to this group, send email to algoge...@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
  .com
  .
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

  --
  With Regards,
  Jalaj Jaiswal
  +919026283397
  B.TECH IT
  IIIT ALLAHABAD

  --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To post to this group, send email to algoge...@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.

 --
 Best Regards
 Ashish Goel
 Think positive and find fuel in failure
 +919985813081
 +919966006652
 Ho

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@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.




-- 
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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.

Re: [algogeeks] Re: Merging of Binary trees

2010-07-26 Thread Manjunath Manohar 
no just a BT, the tree can be in any form..it need not be balanced also..

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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.

Re: [algogeeks] Re: Merging of Binary trees

2010-07-26 Thread jalaj jaiswal 
convert both to dll and merge the two dll's and
finally create the tree from a dll recursively

On Mon, Jul 26, 2010 at 5:16 PM, Manjunath Manohar manjunath.n...@gmail.com
 wrote:

 no just a BT, the tree can be in any form..it need not be balanced also..

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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.

Re: [algogeeks] Re: Merging of Binary trees

2010-07-26 Thread Manjunath Manohar 
@jalaj: could u pls elaborate on that a bit more..will it have the
complexity of O(n logn logn), and also can u provide the pseudocode pls..

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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.

Re: [algogeeks] Re: Merging of Binary trees

2010-07-26 Thread jalaj jaiswal 
suppose both trees contains n nodes
then converting to dll both the trees O(n) + O(n)
then merging two dll's O(n)
converting back to tree also O(2*n)=O(n)..// not sure about it

code for converting tree to dll
node * bsttolist(node *root){
  if(root==NULL) return NULL;
  node *l=bsttolist(root-left);
  node *r=bsttolist(root-right);
  root-left=root;
  root-right=root;
  append(l,root);
  append(l,r);
  return l;
}


here append function merges two circular doubly linked lists , you can make
that on your own




On Mon, Jul 26, 2010 at 5:52 PM, Manjunath Manohar manjunath.n...@gmail.com
 wrote:

 @jalaj: could u pls elaborate on that a bit more..will it have the
 complexity of O(n logn logn), and also can u provide the pseudocode pls..

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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.

Re: [algogeeks] Re: Merging of Binary trees

2010-07-26 Thread Manjunath Manohar 
@jalaj..thanks for ur help..really appreciate it.. :)

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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.

Re: [algogeeks] Re: Merging of Binary trees

2010-07-26 Thread Manjunath Manohar 
@ashish..nice code..i think the complexity is O(n logn ) right.. am i
right??

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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.

Re: [algogeeks] Re: Merging of Binary trees

2010-07-26 Thread Ashish Goel 
Jalaj,

How do you convert a Circular DLL to BST??
Please refer my solution, and coorect it if needed;)


Regards
Ashish


On 7/26/10, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
 suppose both trees contains n nodes
 then converting to dll both the trees O(n) + O(n)
 then merging two dll's O(n)
 converting back to tree also O(2*n)=O(n)..// not sure about it

 code for converting tree to dll
 node * bsttolist(node *root){
   if(root==NULL) return NULL;
   node *l=bsttolist(root-left);
   node *r=bsttolist(root-right);
   root-left=root;
   root-right=root;
   append(l,root);
   append(l,r);
   return l;
 }


 here append function merges two circular doubly linked lists , you can make
 that on your own




 On Mon, Jul 26, 2010 at 5:52 PM, Manjunath Manohar manjunath.n...@gmail.com
 wrote:

 @jalaj: could u pls elaborate on that a bit more..will it have the
 complexity of O(n logn logn), and also can u provide the pseudocode pls..

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 With Regards,
 Jalaj Jaiswal
 +919026283397
 B.TECH IT
 IIIT ALLAHABAD

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@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.




-- 
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
Ho

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@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.