# Need help with mah BSTree (aka jumbled mess)

• 10-05-2007
indigo0086
Need help with mah Binary Search Tree (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.
• 10-05-2007
indigo0086
was it this easy
Code:

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

NO, DO NOT WORK!
• 10-05-2007
indigo0086
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.
• 10-05-2007
indigo0086
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.
• 10-05-2007
indigo0086
Bueller...
• 10-06-2007
indigo0086
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?