C++ Delete node from binary search tree

Question

I have built a binary search tree, and inserted some random value nodes. I am trying to implement a function to delete the nodes, but for some reason it doesn't work. When trying to delete a given node, it seems that the parent node of the deleted node and the child node of the deleted node won't "connect".

Can anyone see what I've done wrong? I've tried debugging the program multiple times to see where my mistake is, but I don't understand how I can link the parent and the child together.

Here's my program:

#include <iostream>
using namespace std;

struct Node
{
    int data;   
    Node* left; 
    Node* right;
};

Node* insertNode(Node* root, int n);
Node* newNode(int d);
Node* deleteNode(Node* root, int d);
Node* findMin(Node* root);

int main()
{
    int num;
    Node* rootPtr = NULL;
    Node* min;

    rootPtr = insertNode(rootPtr, 15);
    rootPtr = insertNode(rootPtr, 10);
    rootPtr = insertNode(rootPtr, 20);
    rootPtr = insertNode(rootPtr, 24);
    rootPtr = insertNode(rootPtr, 7);
    rootPtr = insertNode(rootPtr, 25);
    rootPtr = insertNode(rootPtr, 5);

    rootPtr = deleteNode(rootPtr, 7);

    cout << "\nEnter a number to search for: ";
    cin >> num;
    if(search(rootPtr, num))
        cout << "\nFound.";
    else
        cout << "\nNot found.";

    cout << endl;
    return 0;
}

Node* insertNode(Node* root, int n)
{
    if(root == NULL)                                
        root = newNode(n);                          
    else if(n <= root->data)                        
        root->left = insertNode(root->left, n);     
    else if(n > root->data)                         
        root->right = insertNode(root->right, n);
    return root;                                    
}

Node* newNode(int d)
{
    Node* newNode = new Node();             
    newNode->data = d;                      
    newNode->left = newNode->right = NULL;
    return newNode;                         
}

bool search(Node* root, int d)
{
    if(root == NULL)                    
        return false;
    else if(root->data == d)            
        return true;
    else if(d < root->data)             
        return search(root->left, d);   
    else if(d > root->data)             
        return search(root->right, d);  
}

Node* deleteNode(Node* root, int d)
{
    if(root == NULL)
        return root;
    else if(d < root->data)
        deleteNode(root->left, d);
    else if(d > root->data) 
        deleteNode(root->right, d);
    else
    {
        if(root->left == NULL && root->right == NULL)
        {
            delete root;
            root = NULL;
        }
        else if(root->left == NULL)     
        {
            Node* temp = root;      
            root = root->right;         
            delete temp;                
        }
        else if(root->right == NULL)    
        {
            Node* temp = root;          
            root = root->left;          
            delete temp;                
        }
        else
        {
            Node* temp = findMin(root->right);
            root->data = temp->data;            
            root->right = deleteNode(root->right, temp->data);
        }
    }
    return root;
}

Node* findMin(Node* root)
{
    if(root == NULL)
        cout << "\nThe tree is empty.";
    else
    {
        Node* temp = root;          
        while(temp->left != NULL)   
            temp = temp->left;      
        return temp;                
    }
}

Arun · Accepted Answer · 2016-10-26 13:21:06Z

1

In the deleteNode() function, the nodes are not getting connected in the return path of the recursion. You might need to use the return value of the function like you did for insertNode(). For example,

else if(d < root->data)
    deleteNode(root->left, d);
else if(d > root->data) 
    deleteNode(root->right, d);

might be (something like)

else if(d < root->data)
    root->left = deleteNode(root->left, d);
else if(d > root->data) 
    root->right = deleteNode(root->right, d);

Also, the caller of findMin() might need both the min node and its parent. Let it return both. In deleteNode() you might need to set one of the child pointer of parent to NULL.

answered Oct 26, 2016 at 13:21

Arun

20.6k12 gold badges54 silver badges61 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Donghui Zhang · Accepted Answer · 2016-10-26 13:07:32Z

0

When you delete a node, you also need to set NULL a pointer stored in the parent node.

Say you have node P and C where P.left=C, and C is a leaf node. Your code will deallocate the memory for C, and sets a temporary variable (called root in your program) to NULL. (BTW use nullptr instead of NULL.) But if you examine the content of P, it still refers to the deallocated address of C.

answered Oct 26, 2016 at 13:07

Donghui Zhang

1,1436 silver badges8 bronze badges

2 Comments

Andreas BH Over a year ago

Which part of the parent and when do I set it to NULL (or nullptr)? After deletion of my temp-variable?

Donghui Zhang Over a year ago

In my example, you'll need to change the 'left' field of the parent node. Your deleteNode() algorithm has to keep track of parent, by using a separate temporary variable. And it needs to know whether the node you are deleting is the left child or the right child of the parent node.

Wali Lambert · Accepted Answer · 2021-11-22 15:24:33Z

#include <iostream>
using namespace std;

template<typename T>
class BinaryTree
{
private:
    struct Node
    {
        Node* parent = nullptr;
        Node* left = nullptr;
        Node* right = nullptr;
        T data{};
    };
    Node* root = nullptr;


public:
    Node* get_root() const { return root; }
    const Node* search(const T& _data);
    void insert(const T& _data);
    T find_max(Node* node);
    T find_min(Node* node);
    Node* delete_node(Node* node,T& data);
    void print(Node* node);

};


template <typename T>
const typename BinaryTree<T>::Node* BinaryTree<T>::search(const T& _data) 
{
    Node* current = root;

    while (current)
    {
        if (current->data == _data)
        {
            return current;
        }
        else if (current->data > _data)
        {
            current = current->left;
        }
        else if (current->data < _data)
        {
            current = current->right;
        }
    }
    return nullptr;
}

template <typename T>
void BinaryTree<T>::insert(const T& _data)
{
    Node* current = root;

    if (current == nullptr)
    {
        root = new Node;
        root->data = _data;
        return;
    }

    while (current)
    {
        if (current->data == _data)
        {
            return;
        }
        if (_data > current->data)
        {
            if (current->right == nullptr)
            {
                Node* newNode = new Node();
                newNode->data = _data;
                current->right = newNode;
                newNode->parent = current;
                return;
            }
            current = current->right;
        }
        else if (_data < current->data)
        {
            if (current->left == nullptr)
            {
                Node* newNode = new Node();
                newNode->data = _data;
                current->left = newNode;
                newNode->parent = current;
                return;
            }
            current = current->left;
        }
    }
}


template <typename T>
void BinaryTree<T>::print(Node* node)
{
    if (node != nullptr)
    {
        print(node->left);
        std::cout << node->data << std::endl;
        print(node->right);
    }
}

//not used 
template <typename T>
T BinaryTree<T>::find_max(Node* node)
{
    
    if (node->right != NULL)
    {
        find_max(node->right);
    }
    else {
        cout << node->data << std::endl;
    }
    return node->data;

}

template <typename T>
T BinaryTree<T>::find_min(Node* node)
{
    if (node->left != NULL)
    {
        find_max(node->left);
    }
    else {
        cout << node->data << std::endl;
    }
    return node->data;

}

template <typename T>

typename BinaryTree<T>::Node* BinaryTree<T>::delete_node(Node* node, T& _data)
{
    if (node == NULL) {
        return NULL;
    }
    else if (_data < node->data) {
        node->left = delete_node(node->left, _data);
    }
    else if (_data > node->data) {
        node->right = delete_node(node->right, _data);
    }
    else {
        if (node->left == NULL) {
            Node* temp = node->right;
            delete node;
            return temp;
        }
        else if (node->right == NULL) {
            Node* temp = node->left;
            delete node;
            return temp;
        }
        else {
            node->data = find_min(node->right);
            node->right = delete_node(node->right, node->data);
        }
    }
    return node;
}




int main()
{
    BinaryTree<int> tree;
    int numb{};

    tree.insert(15);
    tree.insert(11);
    tree.insert(100);
    tree.insert(16);
    tree.insert(13);
    tree.insert(18);
    tree.insert(16);
    tree.insert(10);

    tree.print(tree.get_root());
    cout << endl << endl;
    cout << "Max: ";
    tree.find_max(tree.get_root());
    cout << endl << endl;
    cout << "Min: ";
    tree.find_min(tree.get_root());
    tree.print(tree.get_root());
    
    while (tree.search(numb)==nullptr) {
        cout << "Choose Number To Delete: ";
        cin >> numb;
    }
    
    cout << endl << endl;
    tree.delete_node(tree.get_root(), numb);
    tree.print(tree.get_root());

    return 0;
}

Welcome to StackOverflow! Please avoid writing code-only answers: provide some context in addition to your solution.

Collectives™ on Stack Overflow

C++ Delete node from binary search tree

3 Answers 3

Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related