By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,814 Members | 1,678 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,814 IT Pros & Developers. It's quick & easy.

merge two binary trees

P: n/a
please gimme the logic to merge two binary search trees?I mean which
node has to be the root node of the new binary tree??
Thanks in advance

Feb 24 '06 #1
Share this Question
Share on Google+
8 Replies


P: n/a
sudharsan wrote:

please gimme the logic to merge two binary search trees?I mean which
node has to be the root node of the new binary tree??
Thanks in advance


Thanks for monitoring this newsgroup and being aware of what is and
is not topical for it. In the same spirit of co-operation, I offer
the following accurate method:

Install all items in a new tree, using only the left pointer, and
setting all the new right pointers to NULL. Extract the items from
the original trees with an inorder treewalk. When done, sort the
resultant list formed with the left pointers with mergesort. The
result will be a binary search tree.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
Feb 24 '06 #2

P: n/a

CBFalconer wrote:
sudharsan wrote:

please gimme the logic to merge two binary search trees?I mean which
node has to be the root node of the new binary tree??
Thanks in advance


Thanks for monitoring this newsgroup and being aware of what is and
is not topical for it. In the same spirit of co-operation, I offer
the following accurate method:

Install all items in a new tree, using only the left pointer, and
setting all the new right pointers to NULL. Extract the items from
the original trees with an inorder treewalk. When done, sort the
resultant list formed with the left pointers with mergesort. The
result will be a binary search tree.

--

thanks cbfalconer,
but i cudnot understand "Extract the items from
the original trees with an inorder treewalk" original tree???which one
.....of the two sorted binary tree??

Feb 27 '06 #3

P: n/a

sudharsan wrote:
CBFalconer wrote:
sudharsan wrote:

please gimme the logic to merge two binary search trees?I mean which
node has to be the root node of the new binary tree??
Thanks in advance


Thanks for monitoring this newsgroup and being aware of what is and
is not topical for it. In the same spirit of co-operation, I offer
the following accurate method:

Install all items in a new tree, using only the left pointer, and
setting all the new right pointers to NULL. Extract the items from
the original trees with an inorder treewalk. When done, sort the
resultant list formed with the left pointers with mergesort. The
result will be a binary search tree.

--

thanks cbfalconer,
but i cudnot understand "Extract the items from
the original trees with an inorder treewalk" original tree???which one
....of the two sorted binary tree??


You didn't get it did you? Let me spell it out:

Your question is off-topic here. Please take it to a better group. Our
neighbours in comp.programming (down the hall, second door on the
right) may be able to help. When you next have a question that involves
C programming language, feel free to call again.

--
BR, Vladimir

Feb 27 '06 #4

P: n/a
"Vladimir S. Oka" <no****@btopenworld.com> writes:
[...]
Your question is off-topic here. Please take it to a better group. Our
neighbours in comp.programming (down the hall, second door on the
right) may be able to help. When you next have a question that involves
C programming language, feel free to call again.


I thought comp.lang.c++ was the second door on the right. Or did you
go down the hall in the opposite direction?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 27 '06 #5

P: n/a
On 2006-02-27, Keith Thompson <ks***@mib.org> wrote:
"Vladimir S. Oka" <no****@btopenworld.com> writes:
[...]
Your question is off-topic here. Please take it to a better group. Our
neighbours in comp.programming (down the hall, second door on the
right) may be able to help. When you next have a question that involves
C programming language, feel free to call again.


I thought comp.lang.c++ was the second door on the right. Or did you
go down the hall in the opposite direction?


Wouldn't you then say "up the hall"?

Clearly, the second door on the right leads to a dead-end mini-hallway
with two doors in it leading to the rooms in question.
Feb 27 '06 #6

P: n/a
Jordan Abel <ra*******@gmail.com> writes:
On 2006-02-27, Keith Thompson <ks***@mib.org> wrote:
"Vladimir S. Oka" <no****@btopenworld.com> writes:
[...]
Your question is off-topic here. Please take it to a better group. Our
neighbours in comp.programming (down the hall, second door on the
right) may be able to help. When you next have a question that involves
C programming language, feel free to call again.


I thought comp.lang.c++ was the second door on the right. Or did you
go down the hall in the opposite direction?


Wouldn't you then say "up the hall"?


Obviously we're at the high point of the hall, so it's "down" in both
directions.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 27 '06 #7

P: n/a
sudharsan wrote:
CBFalconer wrote:
sudharsan wrote:

please gimme the logic to merge two binary search trees?I mean which
node has to be the root node of the new binary tree??
Thanks in advance


Thanks for monitoring this newsgroup and being aware of what is and
is not topical for it. In the same spirit of co-operation, I offer
the following accurate method:

Install all items in a new tree, using only the left pointer, and
setting all the new right pointers to NULL. Extract the items from
the original trees with an inorder treewalk. When done, sort the
resultant list formed with the left pointers with mergesort. The
result will be a binary search tree.


thanks cbfalconer,
but i cudnot understand "Extract the items from
the original trees with an inorder treewalk" original tree???
which one....of the two sorted binary tree??


The method will work, but will be degenerate. The point is that
the question has nothing to do with the subject of this newsgroup.
If you don't understand you need to do some studying of elementary
algorithms, which again is not topical here. I suggest getting and
reading Sedgwicks "Algorithms" or "Algorithms in C".

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
Feb 27 '06 #8

P: n/a
Keith Thompson wrote:
Jordan Abel <ra*******@gmail.com> writes:
On 2006-02-27, Keith Thompson <ks***@mib.org> wrote:
"Vladimir S. Oka" <no****@btopenworld.com> writes:
[...]
Your question is off-topic here. Please take it to a better group.
Our neighbours in comp.programming (down the hall, second door on
the right) may be able to help. When you next have a question that
involves C programming language, feel free to call again.

I thought comp.lang.c++ was the second door on the right. Or did
you go down the hall in the opposite direction?


Wouldn't you then say "up the hall"?


Obviously we're at the high point of the hall, so it's "down" in
both directions.


You can't go up. Maybe you should drop something, or turn off the
lamp to conserve batteries.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
Feb 28 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion.