Reputation: 365
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
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