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