Thread: Merge two Binary Search Trees

  1. #1
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278

    Merge two Binary Search Trees

    How efficiently can we merge two binary search trees?
    Naive method such as tearing off nodes one by one from 2nd tree and inserting into first tree is not desired.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    Are there any special properties of these two trees we should know about?

    What about special cases, like
    - merging two identical trees
    - merging two trees where a simple root->left = t1 and root->right = t2 suffices


    What are you hoping to gain when you've done it?
    It's still going to be O(logn) whether you search one tree or two trees.

    Unless your trees substantially overlap (which would involve an iterative remove / search / insert anyway), you're not going to reduce n by a significant amount.

    In any event, if you were doing a search, you would stop at search(t1) if what you were looking for was found, and NOT do search(t2), even if t2 happens to also contain what you're looking for.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >How efficiently can we merge two binary search trees?
    O(N + M) where N is the size of the first tree and M is the size of the other. It's done by flattening the trees into arrays, merging the arrays, then generating a new tree from the merged result.
    My best code is written with the delete key.

  4. #4
    Anirban Ghosh
    Join Date
    Jan 2006
    Posts
    278
    But the thing is we are either destroying the trees or using extra space for doing so.
    Can we do in O(log n + log m)? Is it possible?

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >But the thing is we are either destroying the trees or using extra space for doing so.
    Yes, there are no other options. Either you destroy the trees and reuse the memory they take up, or you duplicate the data and use extra space.

    >Can we do in O(log n + log m)? Is it possible?
    No. the best you can do is O(N + M) if the binary search tree ordering property needs to be maintained. You can do it in place by deconstructing the trees as you go, flattening them into degenerate trees (linked lists), and finally merging them in the typical manner. This is essentially the same solution as merging two arrays and creating a new tree, though more complicated due to the breakdown of the original trees mid-process.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search of Array
    By pantherman34 in forum C Programming
    Replies: 21
    Last Post: 05-04-2010, 09:39 AM
  2. Binary Search Trees
    By bleuz in forum C++ Programming
    Replies: 2
    Last Post: 04-30-2010, 01:44 AM
  3. Binary Search Trees
    By lorannex in forum C Programming
    Replies: 3
    Last Post: 04-25-2009, 06:24 AM
  4. Newbie questions regarding binary search trees
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 11-04-2001, 07:48 AM