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
if it is a simple BT then you can simply attach the root to either
child ( which is null ) of other tree . just simply go leftmost and
then assign root of other tree as left child, as suggested by Gene.
On Jul 27, 8:23 am, Gene gene.ress...@gmail.com wrote:
You actually only need a singly linked
Think hard! It's for a slightly different problem, but the same
algorithm works fine. It converts an arbitrarily skewed tree to a
perfectly balanced tree. So you can just walk the two input trees,
deconstruct them into sorted lists (a fully skewed tree is just a
list). Merge the two lists into a
are you asking for BST or simple BT. what are the conditions you want
to follow if simple BT
On Jul 26, 12:59 am, AlgoBoy manjunath.n...@gmail.com wrote:
Does anyone know how to merge two binary trees in O(n logn logn)
complexity..
intiutive solution is to flatten both the trees (by inorder
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
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
@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
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
@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
@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
If the trees are not ordered or balanced, you can do this in O(n)
time. Just walk the nodes of Tree A until you find one with a child
missing and attach Tree B at that location. Some people are confused
by the fact that each individual step of a tree walk can take up to
O(log n) time. But for
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)
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??
13 matches
Mail list logo
