BST Algorithm Copy Only Even Data

I am looking for assistance with an algorithm to copy even data in a BST of integer data. I have a somewhat working algorithm, but it misses some right nodes, and I don't know what I'm doing wrong.

Here is the code. Let me know if you can help:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int table::copy_even(table&dest){
  return copy_even(root, dest.root);
}

int table::copy_even(node*root, node*&dest){ 

  int c = 0;
  if(!root){
    dest = NULL;
    return 0;
  }
  
  if(root->data %2 == 0){
    dest = new node;
    dest->data = root->data;
    dest->left = dest->right = NULL;
    ++c;
    c = copy_even(root->left, dest->left);
    c = copy_even(root->right, dest->right);   
  }
  
  else{
    c = copy_even(root->left, dest);
    if(dest) 
      c = copy_even(root->right, dest->right);
    else 
      c = copy_even(root->right, dest);
  }
  
  return c;
}



Further explanation:
Given a tree like the following (printed from left to right, right subtrees are up, left subtrees are down):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                ---(72)
                                ---(66)
                        ---(38)
                                        ---(33)
                                ---(26)
                                        ---(25)
        ---(20)
                                        ---(17)
                                ---(15)
                        ---(15)
                ---(13)
                                ---(12)
                        ---(9)
                                ---(8)
---(7)
        ---(3)
--------------------------------------------------------------------------------

(root is 7)

it will produce:
1
2
3
4
5
6
7
        ---(72)
                        ---(66)
                ---(38)
                        ---(26)
---(20)
        ---(8)
--------------------------------------------------------------------------------


Effectively losing 9's right node (12) in the left subtree.
Last edited on
it looks like you have the right idea. I don't see the issue, but assuming dest is a new tree, and assuming you already have an insert function, ... you are doing too much here. it should literally be

if(!root) return;
if(root->data%2==0) dest.insert (root->data);
recurse(left)
recurse(right)

and at the end dest would be a new tree with only the even node data.
Which is close to what you have but you are trying to mudge the inserts and the find and the traversal and everything into one recursive function and likely there is a bug in it.

See if you can get it with a reduced approach and if not I will look harder.
Last edited on
Thank you for the input. I know its atypical/unrealistic and given a better class structure, I don't think it would be as much of a problem, but its for a practice system in university.

The system has just a BST generator (random integer data), a node struct, and a table class (with only default ctor, and inorder display). We are assigned, usually weird, questions to work with that system..

This is a practice question for that system, so we are somewhat restricted on what we can implement.

But I think I will go with that, and just try my luck with the grader. It seems far less complex.

Thanks again!
Last edited on
Ok. Some schools seem to delight in making students do things that make no sense.

All I am really saying, if you want to boil it down, is that your function is doing too much and recursion is aggravating to debug. Make it do less by splitting up the problem, is the general idea here, so you can test each piece and find the bugs quickly.
Yeah, the intent (I imagine) is more problem solving. But yeah, some of them are really off the wall and I've gotten berated for trying to get help (stackexchange).

I ended up going with a simple insert function (as you recommended) and everything worked as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int table::insert(int d){
  root = insert(root, d); 
    return 1;
}

node* table::insert(node*root, int d){
  if(!root){
    root = new node;
    root->data = d;
    root->left = root->right = NULL;
    return root;
  }
  
  if(d > root->data) root->right = insert(root->right, d);
  else root->left = insert(root->left, d);
  return root;
}

int table::copy_even(table&dest){
  int c = 0;
  copy_even(root, dest, c);
  return c;
}

void table::copy_even(node*root, table&dest, int&c){

  if(!root) return;
  
  if(root->data % 2 == 0){
    dest.insert(root->data);
    ++c;
  }
 
  copy_even(root->left, dest, c);
  copy_even(root->right, dest, c);
}


Thanks again.
Topic archived. No new replies allowed.