c++ Remove two largest values in a binary tree

[CJPowell27]

Hey guys, I'm trying to practice before a proficiency exam tomorrow and one of the example problems we were given is to solve is to remove the two largest data items in a binary search tree. I'm having a lot of trouble solving all of the special cases for this function. I know how to do it if the largest node does not have any children and the parent of the largest only has the largest as a child, but other than that I really have no idea where to begin, could someone give some advice on the special conditions and/or some example code? I've been trying to solve this for two days now and have made no progress. Below is the setup for my practice functions I've been working on

Spoiler

 

struct node
{
	int data;
  	node * left;
  	node * right;
};

class table
{
	public:
  		table();
  		~table();
  	private:
  		node * root;
}

 

[P4ZD4]

 

start(){
	remove(max(root), root);
	remove(max(root), root);  
}

remove (String key, node position)
{
        if(root == null) return;

        if(position.key > key){
            remove(key, position.left);				//keep searching for key node on left
        }
        else {
            if(position.key < key){
            	remove(key, position.right);			//keep searching for key node on right
          	}
            else {
                                   
                if (position.left != null && position.right != null)
                {
                    next_max_node = max(position.right);
                    position.key = next_max_node.key;
                    remove (next_max_node.key, position.right);	//next goes onto remove next_max_node value
                }
                else if(position.left != null) {
                    position = position.left;
                }
                else if(position.right != null) {
                    position = position.right;
                }
                else {
                    position = null;
                }
      		}
        }
}
                                   
max(node)
{	
    maxnode = node;
	while(maxnode.right != null){
	    maxnode = maxnode.right;
	}                                   
    return maxnode;
}                                 
                                   

 

Edited March 17, 2017 by P4ZD4