CODEWITHSUNDEEP
c++treeiteratorcopybinary-search-tree
TigerCode
TigerCode

Reputation: 365

Binary Search Tree - Copying one tree into another tree

I have a BST that has entries containing a key and string. I've made a tree and populated it values and want to copy its values into another tree. The only functions I have are the common Binary Search Tree functions and Iterators Begin() and End().

How can I do this without using a direct copy function ie. Copy ( T1, T2 )?

I'm just looking for the how to theoretically, not the actual code implementation.

Upvotes: 0

Views: 668

Answers (1)

David Scarlett
David Scarlett

Reputation: 3341

If the only functions you have are search, insert, delete, begin iterator and end iterator, then it sounds like your only option would be to iterate over the first tree, individually inserting each value into the destination tree. But beware that if these iterators return elements in order, and your trees are not self-balancing, then when copied, the resulting tree will be a stick. (i.e. It will be completely unbalanced.) If your iterators return values pre-order or breadth first then this is not a concern.

E.g. Given the following tree:

     4
    / \
   /   \
  2     6
 / \   / \
1   3 5   7

If the iterators returned the sequence 1, 2, 3 ... 7, inserting them in that order into an empty tree would produce the following:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7

However pre-order iterators would return 4, 2, 1, 3, 6, 5, 7, and breath-first iterators would return 4, 2, 6, 1, 3, 5, 7, and either of these insertion orders would reproduce the original tree.

Upvotes: 1

Related Questions