Function to delete all leaf nodes from Binary Search Tree

Question

I would like to ask for corrections on that function. The problem is that it deletes more nodes than there are leaves. Means it is deleting all the leaves first, and then it is deleting the just created leaves. Please, advise me how to correct it. Leaf = node without children nodes.

typedef struct node {
    int key;
    node* left;
    node* right;
}node;

void BST::DeleteLeafs()
{
    if (root == nullptr)
        throw InvalidOperationException();
    else
        deleteLeavesHelper(nullptr, root);
}

void BST::deleteLeavesHelper(node* parent, node* n)
{
    if (n == nullptr)
        return;
    else
    {
        if (n->left == nullptr && n->right == nullptr)
        {
            n = nullptr;
            if (parent != nullptr)
            {
                parent->left = nullptr;
                parent->right = nullptr;
            }
        }
        else
        {
            deleteLeavesHelper(n, n->left);
            deleteLeavesHelper(n, n->right);
        }
    }
}

user31264 user31264 · Accepted Answer · 2016-10-19T05:53:07

You write:

    if (n->left == nullptr && n->right == nullptr)
    {
        n = nullptr;
        if (parent != nullptr)
        {
            parent->left = nullptr;
            parent->right = nullptr;
        }
    }

One problem, you should deallocate the memory for n, otherwise you have a memory leak. n=nullptr; is completely useless.

Another problem, you nullify pointers to both children of parent. Instead, you need to nullify only the pointer to the correct child:

if (n->left == nullptr && n->right == nullptr) {
    if (parent != nullptr) {
        if (parent->left == n)
            parent->left = nullptr;
        else if (parent->right == n)
            arent->right = nullptr;
        else
            // raise some exception
    }
    // deallocate n
}

Function to delete all leaf nodes from Binary Search Tree

1 Answers