473,236 Members | 1,734 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,236 software developers and data experts.

Help : Merging Binary Search Trees

Can someone help me with an algorithm to merge two binary search trees.

One method I thought of was to flatten both the trees into sorted
lists(inorder traversal),merge those two sorted lists, and build a
binary search tree from the new list.
But this seems to be expensive in terms of space. Can this be done more
efficiently ?
Please help me.

Dec 10 '05 #1
3 6517
In article <11**********************@g14g2000cwa.googlegroups .com>,
ptrSriram <sr********@gmail.com> wrote:
Can someone help me with an algorithm to merge two binary search trees. One method I thought of was to flatten both the trees into sorted
lists(inorder traversal),merge those two sorted lists, and build a
binary search tree from the new list.
But this seems to be expensive in terms of space. Can this be done more
efficiently ?


That depends. There are a number of different types of binary trees.
Is there some particular property imposed on the trees you are
using, such as that they must be "balanced" ? Do your tree entries
have back-pointers or just downward pointers?
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers
Dec 10 '05 #2
Walter Roberson wrote:
ptrSriram <sr********@gmail.com> wrote:
Can someone help me with an algorithm to merge two binary
search trees.

One method I thought of was to flatten both the trees into
sorted lists(inorder traversal),merge those two sorted lists,
and build a binary search tree from the new list. But this
seems to be expensive in terms of space. Can this be done
more efficiently ?


That depends. There are a number of different types of binary
trees. Is there some particular property imposed on the trees
you are using, such as that they must be "balanced" ? Do your
tree entries have back-pointers or just downward pointers?


I think the question should be answered in terms of a minimal
organization. i.e. the fundamental data item should be very
similar to:

struct itemlink {
struct itemlink *left, *right;
void *dataptr;
};

together with some routine that will return a -1, 0, +1 comparison
result when passed two struct itemlink * pointers. Then the trees
to be merged are represented by two struct itemlink * pointers to
the roots of the two trees.

--
Read about the Sony stealthware that is a security leak, phones
home, and is generally illegal in most parts of the world. Also
the apparent connivance of the various security software firms.
http://www.schneier.com/blog/archive...drm_rootk.html
Dec 11 '05 #3
ptrSriram wrote:
Can someone help me with an algorithm to merge two binary search trees.

One method I thought of was to flatten both the trees into sorted
lists(inorder traversal),merge those two sorted lists, and build a
binary search tree from the new list.
But this seems to be expensive in terms of space.


Why would it be expensive in space? If the data is in a tree, each item
should be held in a node with two or more pointers. You should be able
to link the items into list, merge them, and place them in another tree
without any additional space.

--
Thad

Dec 12 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

12
by: Vibhajha | last post by:
Hi friends, My sister is in great problem , she has this exam of C++ and she is stuck up with some questions, if friends like this group provides some help to her, she will be very grateful....
3
by: tsunami | last post by:
hi all; I have an array and want to insert all the elements from this array to a binary search tree.That array is an object of the class of a stringtype which includes overloaded "< > = =="...
8
by: sudharsan | last post by:
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
10
by: free2cric | last post by:
Hi, I have a single link list which is sorted. structure of which is like typedef struct mylist { int num; struct mylist *next;
2
by: pyguy | last post by:
Hi all, I am running into a conceptual glitch in implementing a simple binary tree class. My insertion and printing (sorting) seems to be ok, but when I search the tree, my find method isn't doing...
4
by: gagan.singh.arora | last post by:
I had a test today and there was a question regarding how to merge two AVL trees to form another AVL tree without using any AVL tree operations. Some had done it by using an array, sorted the...
6
by: Henrik Goldman | last post by:
Hello, I have a dataset which consist of a string username and string hostname as a key and then an integer representing a count as the matching "second" value in a pair. So far I've used...
7
by: Vinodh | last post by:
Started reading about Binary Trees and got the following questions in mind. Please help. Definition of a Binary Tree from "Data Structures using C and C++ by Tanenbaum" goes like this, "A...
1
by: mark | last post by:
I have a 5x5 Matrix. Each cell consists a string value(ex:URL of a website) I want to find out which string value occurs( i.e. repeats ) maximum no. of times in the matrix. I have a hint...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.