Need help with mah BSTree (aka jumbled mess)

Okay, I'm finishing up my Binary Search Tree implementation that I'm doing out of boredom. The one thing that I'm having trouble on is a delete algorithm that isn't recursive. Most cases work great. When the deleted node has only one subtree (left or right), deleting a leaf, and for the most part deleting a node with two subtrees works alright. Here is my implementation. If it's too messy, tell me, I'll clean it up and repost it :(. But I'll hilight the problem area

Code:

---

template <typename T>
void BSTree<T>::Delete(T x)
{
    if (root == NULL)
    {
        std::cout << "-- Tree is empty --" << std::endl;
        return;
    }

    BinaryTreeNode<T>* prev = root;    //points to previous node
    BinaryTreeNode<T>* next = root;    //points ahead
    size_t dir = 0;                //globally stores pointer direction

    while (true)
    {
        if(next == NULL)
        {
            std::cout << "-- " << x << " not found --" << std::endl;
            return;
        }
        else if (next->data == x)    //if the data has been found and...
        {
            //...both children are null
            if (next->child[0] == NULL && next->child[1] == NULL)
            {
                if (next == root)  //delete if data is at root
                    root = NULL;
                else
                    prev->child[dir] = NULL;

                delete next;
            }
            else if (next->child[0] == NULL)    //...the left child is null
            {
                if (next == root)
                {
                    root = next->child[1];  //point root to it's only child
                }
                else
                    prev->child[dir] = next->child[1];

                next->child[1] = NULL;
                delete next;
            }
            else if (next->child[1] == NULL)    //...the right child is null
            {
                if (next == root)
                    root = next->child[0];
                else
                    prev->child[dir] = next->child[0];

                next->child[0] = NULL;
                delete next;
            }
            else    //...neither child is null
            {
                //pointers to right subtree
                BinaryTreeNode<T>* prevR = next->child[1];
                BinaryTreeNode<T>* nextR = prevR;

                //find the smallest node in right subtree and replace
                while (true)
                {
                    if (nextR->child[0] == NULL)
                    {
                        //Connect smallest node's parent
                        //with smallest node's right child
                        //will be null if no right child exists
                        prevR->child[0] = nextR->child[1];

                        //replace node
                        next->data = nextR->data;

                        //if the rightmost node has no children
                        //set next's right child to NULL
                        if (prevR == nextR && nextR->child[1] == NULL)
                            next->child[1] = NULL;
                        else
                            next->child[1] = nextR->child[1];

                        //nullify node's children array
                        nextR->child[0] = nextR->child[1] = NULL;
                        delete nextR;
                        break;
                    }
                    else
                    {
                        prevR = nextR;
                        nextR = nextR->child[0];
                    }
                }
            }

            std::cout << "-- " << x << " has been deleted --" << std::endl;
            return;
        }
        else
        {
            prev = next;
            dir = x < next->data ? 0 : 1;
            next = next->child[dir];
        }
    }
}

---

If my tree/subtree is in the form

------O
-----/-\
----O---O

nd I need to delete the root of that tree, I have a problem with the getting the root of that tree to have their right child nulled. What I'm basically saying is that is there a more "modular" way to implement this without being recursive, and without confusing myself by trying to find clever ways to make use of as few pointers as possible.

Edit: Okay new and improved BST deletion, if there's anything missing which I can't tell at the moment please advise me on some ways to improve it.

was it this easy

Code:

---

                        if(prevR == nextR)
                            next->child[1] = NULL;

---

NO, DO NOT WORK!

Never mind, fixed it. The problem was with my BinaryTreeNode destructors, they destroy their left and right child, so I had to go back and re-route all the references the node to be deleted had with any node that was to stay in the tree.

And the above code did work, the destructors were the problem.

Ok the above code didn't work, if the tree was in the form:

[FONT=Courier New]------(x)
-----/---\
----O-----O
---/-------\
--O---------O

where I am to delete x then there is a problem, so I changed it to.

Code:

---

                        //if the rightmost node has no right children
                        //set next's right child to NULL, otherwise, point
                        //next's right child to nextR's right child.
                        if (prevR == nextR && nextR->child[1] == NULL)
                            next->child[1] = NULL;
                        else
                            next->child[1] = nextR->child[1];

---

[/code]

it just seems like I'm building a state machine rather than intuitively making routines for the damn thing.

Bueller...

Now I'm goign to work on the traversals. What I want to know is there a nonrecursive method to this, or are the walks pretty much only practical using recursion?