Binary Search Tree deletion

This is a discussion on Binary Search Tree deletion within the C++ Programming forums, part of the General Programming Boards category; I'm writing an iterative delete method for my BST class. I'm a little confused on what to do when I've ...

  1. #1
    Some Guy
    Join Date
    Jul 2004
    Posts
    32

    Binary Search Tree deletion

    I'm writing an iterative delete method for my BST class. I'm a little confused on what to do when I've found the node and I want to delete it. I've developed this small code and I've removed the other sections of code so I can show the problem I'm having.

    The question I have is... should I delete curr as I'm doing? Or should I simply set it to NULL? I'm pretty sure I have to delete the current node, but if I do, the results aren't correct. If I just make current NULL, it's fine. I'm pretty sure my other functions are correct. Any help is appreciated.

    Code:
    // code for 2 children and zero children here (which I haven't written)
    ...
    ...
    
    // code for the case when there is only one child
    // curr points to the node being deleted
    else {
        if (curr == root) {
            // update root to be the child
            root = (curr->left != NULL) ? curr->left : curr->right;
            delete curr;
            curr = NULL;
        }
    }

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Did you use new to create the nodes? If yes, then you need to delete them when you are done.

    My guess is that there are other places that point at the node being deleted. If you delete that node, those other places cause a failure. If you just null it out, then the other places still point at valid memory. The solution would be to make sure you delete the node once and null out all pointers to it.

    Also note that your comment says that you are deleting the child of the current node, but the actual code is deleting the current node and setting the root to the child.

  3. #3
    Some Guy
    Join Date
    Jul 2004
    Posts
    32
    Ah yes... I made sure that all the other pointers were set properly and set the current's data members (left, right, data) equal to NULL and then deleted current. That seems to be working just fine. Thanks Daved.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21