I need help creating a delete function for binary tree.
This is what I have so far... (Last function is what I'm working on)

#include <iostream>
#include <cassert>

namespace CS61
{

	template <class Item, std::size_t MAX>
	class btreenode
	{

	private:
		
		std::size_t used;      // actual number of values in this node
		Item data_field[MAX + 1];  // contains sorted values of this node
		                       // at data_field[0], data_field[1], ...
				       //    data_field[used-1]
		btreenode * children_field[MAX + 2];
					// subtree i contains values
					// > data_field[i-1] and <= data_field[i]


	public:
		btreenode()
		{
			used = 0;
		}

		btreenode(const Item & entry, btreenode *left, btreenode *right) 
		{
			data_field[0] = entry;
			children_field[0] = left;
			children_field[1] = right;
			used = 1;
		}



		// pre: none
		// post: returns the number of values stored in this node
		std::size_t size() const
		{
			return used;
		}

		bool full() const
		{
			return (used == MAX + 1);
		}

		// pre: 0 <= i < used
		// post: return data_field[i]
		const Item & data(std::size_t i) const
		{
			assert(i < used);
			return data_field[i];
		}

		Item & data(std::size_t i)
		{
			assert(i < used);
			return data_field[i];
		}

		const btreenode * child(std::size_t i) const
		{
			assert(i <= used);
			return children_field[i];
		}

		btreenode * child(std::size_t i)
		{
			assert(i <= used);
			return children_field[i];
		}


		void set_child(std::size_t i, btreenode * newchild)
		{
			assert (i <= used);
			children_field[i] = newchild;
		}


		// pre: none
		// post:  return true iff target is a value stored in this node
		//        pos = the index of the first value in this node >= target

		bool is_member(const Item &target, std::size_t & pos)
		{
			for (pos = 0; pos < used; ++pos)
			{
				if (data_field[pos] == target)
					return true;
				if (data_field[pos] > target)
					return false;
			}
			return false;
		}

		// pre: node
		// post: target has been added to this node in sorted order
		//       left and right are its children to the left and right resp.

		void add(const Item &entry, btreenode<Item, MAX> *left, btreenode<Item, MAX> *right)
		{
			assert(used <= MAX);
			std::size_t i;
			for (i = used; i > 0 && data_field[i-1] > entry; --i)
			{
				data_field[i] = data_field[i-1];
				children_field[i+1] = children_field[i];
			}
			data_field[i] = entry;
			children_field[i+1] = right;
			children_field[i] = left;
			++used;
		}

		void remove(std::size_t pos)
		{
			assert(pos < used);
			copy(data_field+pos+1, data_field+used, data_field+pos);
			copy(children_field+pos+1, children_field+used+1, children_field+pos);
			--used;
		}

		void split(Item & middle, btreenode * & left, btreenode * & right)
		{
			assert(used == MAX + 1 && MAX % 2 == 0);
			std::size_t newsize = MAX /2;

			left = new btreenode();
			right = new btreenode();

			std::copy(data_field, data_field + newsize, left->data_field);
			std::copy(children_field, children_field + newsize + 1, left->children_field);
			left->used = newsize;

			
			std::copy(data_field+newsize+1, data_field + used, right->data_field);
			std::copy(children_field+newsize+1, children_field + used + 1, right->children_field);
			right->used = newsize;

			middle = data_field[newsize];
		}

	};

	template <class Item, std::size_t MAX>
	void btree_right_rotate(btreenode<Item, MAX> * & root, std::size_t pos)
	{
		assert(root != NULL && pos < root->size());
		btreenode<Item, MAX> *left = root->child(pos), *right = root->child(pos+1);
		std::size_t ls = left->size(), rs = right->size();
		assert(ls > MAX/2 && rs < MAX);

		right->add(root->data(pos), left->child(ls), right->child(0));
		root->data(pos) = left->child(ls-1);
		left->remove(ls-1);
	}

	template <class Item, std::size_t MAX>
	void btree_left_rotate(btreenode<Item, MAX> * & root, std::size_t pos)
	{
		assert(root != NULL && pos < root->size());
		btreenode<Item, MAX> *left = root->child(pos), *right = root->child(pos+1);
		std::size_t ls = left->size(), rs = right->size();
		assert(ls < MAX && rs > MAX/2);
		left->add(root->data(pos), left->child(rs), right->child(0));
		root->data(pos) = right->child(0);
		right->remove(0);
	}


	template <class Item, std::size_t MAX>
	Item & btree_max(btreenode<Item, MAX> * root)
	{
		assert(root != NULL);
		std::size_t n = root->size();
		if (root->child(n) == NULL)
			return root->data(n-1);
		return btree_max(root->child(n));	
	}

	template <class Item, std::size_t MAX>
	bool btree_find(btreenode<Item, MAX> * root, const Item & target)
	{

		if (root == NULL)
			return false;


		std::size_t i = 0;
		if (root->is_member(target, i))
			return true;
		else
			return btree_find(root->child(i), target);
	}

	template <class Item, std::size_t MAX>
	int btree_depth(const btreenode<Item, MAX> * root)
	{
		if (root == NULL)
			return -1;
		return 1+ btree_depth(root->child(0));
	}

	template <class Item, std::size_t MAX>
        btreenode<Item, MAX>*  btree_insert(btreenode<Item, MAX> * & root, const Item & entry)
	{
		if (root == NULL)
		{
			root = new btreenode<Item, MAX>(entry, NULL, NULL);
			return root;
		}

		std::size_t pos;
		root->is_member(entry, pos);
		btreenode<Item, MAX> *t = root->child(pos);
		btreenode<Item, MAX> *promoted = btree_insert(t, entry);
	
		if (promoted != NULL)
		{
			root->add(promoted->data(0), promoted->child(0), promoted->child(1));
			if (root->full())
			{
				Item middle;
				btreenode<Item, MAX> *left, *right;
				root->split(middle, left, right);
				delete root;
				return new btreenode<Item, MAX>(middle, left, right);
			}
			else
				return NULL;
		}
		else
			return NULL;
	}



	template <class Item, std::size_t MAX>
	void btree_delete(btreenode<Item, MAX> * & root, const Item & target)
	{
		if (root == NULL)
			return;
                
		std::size_t pos;
		if (!root->is_member(target, pos))
		{
			btree_delete(root->child(pos), target);
			return;
		}
                else
                {
		if (root->child(pos) == NULL)
                    {
                    remove(target);
                    return;
                    }
                else
                    {

Here is my updated function...
Where did I go wrong?

#include <iostream>
#include <cassert>

namespace CS61
{

    template <class Item, std::size_t MAX>
            class btreenode
    {

    private:

        std::size_t used;      // actual number of values in this node
        Item data_field[MAX + 1];  // contains sorted values of this node
        // at data_field[0], data_field[1], ...
        //    data_field[used-1]
        btreenode * children_field[MAX + 2];
        // subtree i contains values
        // > data_field[i-1] and <= data_field[i]


    public:
        btreenode()
        {
            used = 0;
        }

        btreenode(const Item & entry, btreenode *left, btreenode *right)
        {
            data_field[0] = entry;
            children_field[0] = left;
            children_field[1] = right;
            used = 1;
        }



        // pre: none
        // post: returns the number of values stored in this node
        std::size_t size() const
        {
            return used;
        }

        bool full() const
        {
            return (used == MAX + 1);
        }

        // pre: 0 <= i < used
        // post: return data_field[i]
        const Item & data(std::size_t i) const
        {
            assert(i < used);
            return data_field[i];
        }

        Item & data(std::size_t i)
        {
            assert(i < used);
            return data_field[i];
        }

        const btreenode * child(std::size_t i) const
        {
            assert(i <= used);
            return children_field[i];
        }

        btreenode * child(std::size_t i)
        {
            assert(i <= used);
            return children_field[i];
        }


        void set_child(std::size_t i, btreenode * newchild)
        {
            assert (i <= used);
            children_field[i] = newchild;
        }


        // pre: none
        // post:  return true iff target is a value stored in this node
        //        pos = the index of the first value in this node >= target

        bool is_member(const Item &target, std::size_t & pos)
        {
            for (pos = 0; pos < used; ++pos)
            {
                if (data_field[pos] == target)
                    return true;
                if (data_field[pos] > target)
                    return false;
            }
            return false;
        }

        // pre: node
        // post: target has been added to this node in sorted order
        //       left and right are its children to the left and right resp.

        void add(const Item &entry, btreenode<Item, MAX> *left, btreenode<Item, MAX> *right)
        {
            assert(used <= MAX);
            std::size_t i;
            for (i = used; i > 0 && data_field[i-1] > entry; --i)
            {
                data_field[i] = data_field[i-1];
                children_field[i+1] = children_field[i];
            }
            data_field[i] = entry;
            children_field[i+1] = right;
            children_field[i] = left;
            ++used;
        }

        void remove(std::size_t pos)
        {
            assert(pos < used);
            copy(data_field+pos+1, data_field+used, data_field+pos);
            copy(children_field+pos+1, children_field+used+1, children_field+pos);
            --used;
        }

        void split(Item & middle, btreenode * & left, btreenode * & right)
        {
            assert(used == MAX + 1 && MAX % 2 == 0);
            std::size_t newsize = MAX /2;

            left = new btreenode();
            right = new btreenode();

            std::copy(data_field, data_field + newsize, left->data_field);
            std::copy(children_field, children_field + newsize + 1, left->children_field);
            left->used = newsize;


            std::copy(data_field+newsize+1, data_field + used, right->data_field);
            std::copy(children_field+newsize+1, children_field + used + 1, right->children_field);
            right->used = newsize;

            middle = data_field[newsize];
        }

    };

    template <class Item, std::size_t MAX>
            void btree_right_rotate(btreenode<Item, MAX> * & root, std::size_t pos)
    {
        assert(root != NULL && pos < root->size());
        btreenode<Item, MAX> *left = root->child(pos), *right = root->child(pos+1);
        std::size_t ls = left->size(), rs = right->size();
        assert(ls > MAX/2 && rs < MAX);

        right->add(root->data(pos), left->child(ls), right->child(0));
        root->data(pos) = left->child(ls-1);
        left->remove(ls-1);
    }

    template <class Item, std::size_t MAX>
            void btree_left_rotate(btreenode<Item, MAX> * & root, std::size_t pos)
    {
        assert(root != NULL && pos < root->size());
        btreenode<Item, MAX> *left = root->child(pos), *right = root->child(pos+1);
        std::size_t ls = left->size(), rs = right->size();
        assert(ls < MAX && rs > MAX/2);
        left->add(root->data(pos), left->child(rs), right->child(0));
        root->data(pos) = right->child(0);
        right->remove(0);
    }


    template <class Item, std::size_t MAX>
            Item & btree_max(btreenode<Item, MAX> * root)
    {
        assert(root != NULL);
        std::size_t n = root->size();
        if (root->child(n) == NULL)
            return root->data(n-1);
        return btree_max(root->child(n));
    }

    template <class Item, std::size_t MAX>
            bool btree_find(btreenode<Item, MAX> * root, const Item & target)
    {

        if (root == NULL)
            return false;


        std::size_t i = 0;
        if (root->is_member(target, i))
            return true;
        else
            return btree_find(root->child(i), target);
    }

    template <class Item, std::size_t MAX>
            int btree_depth(const btreenode<Item, MAX> * root)
    {
        if (root == NULL)
            return -1;
        return 1+ btree_depth(root->child(0));
    }

    template <class Item, std::size_t MAX>
            btreenode<Item, MAX>*  btree_insert(btreenode<Item, MAX> * & root, const Item & entry)
    {
        if (root == NULL)
        {
            root = new btreenode<Item, MAX>(entry, NULL, NULL);
            return root;
        }

        std::size_t pos;
        root->is_member(entry, pos);
        btreenode<Item, MAX> *t = root->child(pos);
        btreenode<Item, MAX> *promoted = btree_insert(t, entry);
	
        if (promoted != NULL)
        {
            root->add(promoted->data(0), promoted->child(0), promoted->child(1));
            if (root->full())
            {
                Item middle;
                btreenode<Item, MAX> *left, *right;
                root->split(middle, left, right);
                delete root;
                return new btreenode<Item, MAX>(middle, left, right);
            }
            else
                return NULL;
        }
        else
            return NULL;
    }



    template <class Item, std::size_t MAX>
    void btree_delete(btreenode<Item, MAX> * & root, const Item & target)
    {
        if (root == NULL)
            return;

        std::size_t pos;
        if (!root->is_member(target, pos))
        {
            btree_delete(root->child(pos), target);

            if (root->child(pos)<MAX/2)
            {
                if (root->child(pos-1)->size()>MAX/2)
                {
                    btree_right_rotate(root, pos-1);
                    return;
                }
                if(root->child(pos+1)->size()>MAX/2)
                {
                    btree_left_rotate(root,pos);
                    return;
                }
                if(root->child(pos-1)!=NULL)
                {
                    merge_right(root->child(pos-1), root->data(pos), root->child(pos) );
                    if(root=NULL)
                        root=root->child(pos-1);
                    return;
                }

            }
            return;
        }
        else
        {
            if (root->child(pos) == NULL)
            {
                remove(target);
                return;
            }
            else
            {
                target=max(root->child(pos) );
                remove(root->child(pos));
            }

        }
    }
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.