C++ Algorithm to Copy a BST (except the largest data-member) Recursively

[confundido]

I am trying to figure out a bunch of practice problems involving Binary Search Trees and recursion. A lot of them are like "Copy an entire BST except..." and then some stipulation, like except the largest (all the way to the right), except the smallest (all the way to the left), except the two largest, etc.

The last stipulation is to do the requested action in a single recursive call. The practice program uses a randomly generated BST of random integer data (and random size).

I am trying to get started practicing on what I feel is one of the easier ones, copy all but max. I imagine the solution is some combination of two of my algorithms (one is to remove the max node, the other is just a copy).

Here is what I have so far, if anyone can help me with advice on how to tackle this:
COPY

int table::copy(table&dest){

  int count = 0;
  dest.root = copy(root, dest.root, count);
  return count;
}

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

  if(!root) 
    return NULL;
  
  dest = new node;
  dest->data = root->data;
  ++count;
  
  dest->left = copy(root->left, dest->left, count);
  dest->right = copy(root->right, dest->right, count);
  
  return dest;
}

REMOVE_MAX

int table::remove_max(){
  root = remove_max(root);
  return 1;
}

node* table::remove_max(node*root){
  if(!root->right){
    if(root->left){
      node*temp = root;
      root = root->left;
      delete temp;
      return root;
    }
    
    delete root;
    return NULL;
  }
  
  root->right = remove_max(root->right);
  return root;
}

[akash16]

Hi,
Problem statement not clear.

What I understood is, You need to make a copy of given BST except a node having max value.

Is it correct? Else correct me.

[dutch]

Your copy code is a little wacky. There's no point in passing 'dest' around. It's just a local variable. Maybe something like this (untested):

table table::copy() {
  table t;
  t.root = copy(root);
  t.count = count;
  return t;
}

// Note that this should be a 'static' function in table
node* table::copy(node* nd) {
  return nd ? new node(nd->data, copy(nd->left), copy(nd->right)) : nullptr;
}

// assuming ctor like this:
struct node {
    int data;
    node *left, *right;

    node(int data, node* left, node* right)
        : data(data), left(left), right(right)
    { }
};

As for removing the highest node, something like:

void remove_highest(node*& nd) {  // Note we're passing a reference to the pointer
    if (!nd) return;
    if (nd->right)
        remove_highest(nd->right);
    else {
        node* left = nd->left;
        delete nd;
        nd = left;
    }
}

[confundido]

Thank you for the suggestions. Sorry for being unclear.

Do you have any suggestions for combining the two functions?

The idea is to traverse the data structure only once, otherwise its not that difficult to just remove the max.

[dutch]

class table {
    static node* copy_all_but_highest(node* nd, bool right = true);
    table(node* root, size_t count);
    //...
public:
    table table::copy_all_but_highest() {
        return table(copy_all_but_highest(root), count ? count - 1 : 0);
    }
    //...
private:
    node* root;
    size_t count;
}

node* table::copy_all_but_highest(node* nd, bool right) {
    if (right && nd && !nd->right) nd = nd->left;
    return nd ? new node(nd->data,
                         copy_all_but_highest(nd->left, false),
                         copy_all_but_highest(nd->right, right))
              : nullptr;
}

[confundido]

Thank you for the assistance. I ended up going with a less efficient solution.

A lot of the suggestions were beyond the scope of what we were allowed to change (like the constructor), and were not allowed to use ternary operators because were told they make things unreadable, and cause errors if precedence is not managed properly.

Thanks again!