Binary Search Tree Split() function

[j]

Hi,
Anyone out there with binary search tree experience. Working on a
project due tomorrow and really stuck. We need a function that splits
a binary tree into a bigger one and smaller one(for a random binary
search tree. We've tried everything but are in the land of pointer
hell. If someone could help it would be a huge help. our code follows.
We've tried 2 diff methods the split() and splitter() functions

#include <iostream>
#include <stdlib.h>

#ifndef BINTREE_H
#define BINTREE_H

using namespace std;

class binTreeNode{

public:
int data; //stored value
int treeSize; //the size of the key at the current node
binTreeNode *leftchild; //pointer to left node
binTreeNode *rightchild; //pointer to right node

binTreeNode(int a, binTreeNode* L, binTreeNode* R,int treeSize){
data = a; //set the key value
leftchild = L; //set the children to ptrs passed
rightchild = R;
//treeSize=1; //set the size of this "tree" to be 1
this->treeSize = treeSize;
}

binTreeNode(int a){
data = a; //set the key value
leftchild = NULL; //set the children to NULL
rightchild = NULL;
treeSize = 1; //set the size of this "tree" to be 1
}

binTreeNode(){}
//binTreeNode & operator=(binTreeNode &node){
friend class binTree;
};

class binTree{

public:

binTree(int key); //constructor
//~binTree(void); //deconstructor

binTreeNode* copyNode(binTreeNode* n);
void print();

//void printNode(binTreeNode *node);
void printTree(binTreeNode *node);

int cRand(int treeSize); //generate a random number between 0 and
the height of the tree

void insert(int key); //public function that will call insert(int
key, binTreeNode* t)
void insert(int key, binTreeNode* &t); //insert a new node into the
tree

bool search(int key); //public version of the search function
binTreeNode* search(int key, binTreeNode *t); //return a pointer to
the node containing value of key
binTreeNode* searchMin(binTreeNode *t); //returns the smallest value
in a subtree
//binTreeNode* splitter(binTreeNode* &less, binTreeNode* &gtr,
binTreeNode *r, int key);
binTreeNode* splitter(int key, binTreeNode *t, binTreeNode* s,
binTreeNode* g);
binTreeNode insertRoot(int key, binTreeNode* &t);
void split(int key, binTreeNode* &t, binTreeNode *s, binTreeNode
*g); //function used by insertRoot() to split the tree

void deleteNode(int key); //remove public function
void deleteNode(int key, binTreeNode* &t);

int smallest();

private:

binTreeNode *root; //pointer to root node

//int m_height; //height of tree
};

#endif

AND NOW THE IMPLEMENTATION---------------------------------------------------
binTreeNode* binTree::splitter(int key, binTreeNode *t, binTreeNode*
s, binTreeNode* g){
//binTreeNode root;
if(t == NULL){
//less = gtr = NULL;
return NULL;
}
root = new binTreeNode(t->data, t->leftchild, t->rightchild,
t->treeSize);
if(t->data < key) {
//*less = copyNoderoot;
//binTreeNode* temp;
//temp = &(copyNode(root));
//s = temp;//&(copyNode(root));
s = copyNode(root);
return splitter(key, t->leftchild, s, g->leftchild);
//splitter(key, t->leftchild, s, g->leftchild);
//less = copyNode(root);
//return splitter(root->rightchild, gtr, r->rightchild, key);
}else if(t->data > key) {
g = copyNode(root);
return splitter(key, t->rightchild, s->rightchild, g);
//return splitter(less, root->leftchild, r->leftchild, key);
}else{
s = t->leftchild;
g = t->rightchild;
return root;
}
}

binTreeNode binTree::insertRoot(int key, binTreeNode* &t){
binTreeNode s;
binTreeNode g;
//s = NULL;
//g = NULL;
cout << "calling split" << endl;
//splitter(s, g, t, key);
splitter(key, t, &s, &g);
cout << "returning from split" << endl;

t = new binTreeNode();
t->data = key;
//t->rightchild = s;
//t->leftchild = g;
return *t;
}