CODEWITHSUNDEEP
c++pointerswhile-loopbinary-tree
54skyxenon
54skyxenon

Reputation: 27

Trouble with deleting a binary tree non-recursively

Alex Allain's Jumping Into C++ has assigned me the incredulous task of deleting a binary search tree non-recursively (Ch. 17). I came up with a way to simplify this task by modifying my structure definition so that it includes a pointer to the parent node, rather than simply the left and right pointers. I try to avoid using a stack/linked list data structure.

My algorithm for accomplishing this is:

  1. Checking if the current node's L and R pointers are both NULL
  2. If so delete that node and go to the parent node.
  3. If not, go to the L and R nodes until step 1 is achieved (left goes first if L/R pointers are both occupied)
  4. My algorithm concludes when we've hit a NULL parent node (the root node's parent is NULL)

The problem is that I get stuck in an infinite while loop. I doubt that my insert() function is defective, but I could be wrong.

The following code includes all the functions/structures mentioned thus far:

struct node
{
    int key_value;
    node *p_left;
    node *p_right;
    node *parent;
};

node* insert (node *p_tree, int key, node* parent)
{
    if ( p_tree == NULL )
    {
        node* p_new_tree = new node;
        p_new_tree->p_left = NULL;
        p_new_tree->p_right = NULL;
        p_new_tree->key_value = key;
        p_new_tree->parent = parent;
        return p_new_tree;
    }

    else if( key < p_tree->key_value )
        p_tree->p_left = insert( p_tree->p_left, key, p_tree );

    else
        p_tree->p_right = insert( p_tree->p_right, key, p_tree );

    return p_tree;
}

void destroy_tree_Iteratively(node* p_tree)
{
    int nodesDestroyed = 0; //checking to see if I delete the right amount

    while (p_tree != NULL)
    {
        if (p_tree->p_left == NULL && p_tree->p_right == NULL)
        {
            node* placeHolder = p_tree->parent;
            delete p_tree;
            p_tree = placeHolder;
        }
        else if (p_tree->p_left != NULL)
            p_tree = p_tree->p_left;
        else if (p_tree->p_right != NULL)
            p_tree = p_tree->p_right;
    }

    cout << "You've deleted " << nodesDestroyed << " nodes!" << endl;
}

Upvotes: 0

Views: 450

Answers (1)

user207421
user207421

Reputation: 310850

When you delete a node you need to null out its pointer from the parent, whichever of the left and right pointers points to it. If there is a parent. Otherwise the first if test is never true, and you'll just keep traversing forever.

Upvotes: 1

Related Questions