Question

Implement a function to remove a leaf node from a binary search tree. Using the following class and function definition:

class BTNode {
public:
   int item;
   BTNode *left;
   BTNode *right;
   BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){}
};

BTNode *root = nullptr;

BTNode * remove_leaf(int item, bool &removed) {
     // implement
}

The remove function will return the node with the item if it's present in the tree. If the node is a leaf node and is removed by the function, it sets removed=true. Otherwise, if not removed because it is not a leaf node, it sets removed=false. In either case, the function should return a pointer to the node if present in the tree; if not present, return nullptr.

#include <iostream>

class BTNode {
public:
int item;
BTNode *left;
BTNode *right;
BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){}
};

BTNode *root = nullptr;

BTNode * remove_leaf(int item, bool &removed) {

removed = false;   
return nullptr;
}

int main()
{
root = new BTNode(50, new BTNode(25), new BTNode(100));
bool r=false;

BTNode *tmp50 = remove_leaf(50,r);
if (tmp50 == nullptr || r == true) {
std::cout << "Should not have removed node 50! It has a child node." << std::endl;
} else if (!r) {
std::cout << "Correctly chose not to remove node 50." << std::endl;
}

BTNode *tmp100 = remove_leaf(100,r);
if (tmp100 == nullptr || r == false) {
std::cout << "Should have removed node 100! It is a leaf node." << std::endl;
} else if (r) {
std::cout << "Correctly chose to remove node 100." << std::endl;
}

BTNode *tmp25 = remove_leaf(25,r);
if (tmp25 == nullptr || r == false) {
std::cout << "Should have removed node 25! It is a leaf node." << std::endl;
} else if (r) {
std::cout << "Correctly chose to remove node 25." << std::endl;
}

tmp50 = remove_leaf(50,r);
if (tmp50 == nullptr || r == false) {
std::cout << "Should have removed node 50! It is a leaf node." << std::endl;
} else if (r) {
std::cout << "Correctly chose to remove node 50." << std::endl;
}
if (root!=nullptr) {
std::cout << "root should be nullptr now, but it isn't!" << std::endl;
} else {
std::cout << "Correctly set root to nullptr." << std::endl;
}

return 0;
}

Answer 1

#include <iostream>
using namespace std;

class BTNode
{
public:
    int item;
    BTNode *left;
    BTNode *right;
    BTNode(int i, BTNode *l = nullptr, BTNode *r = nullptr) : item(i), left(l), right(r) {}
};

BTNode *root = nullptr;

BTNode *remove_leaf(int item, bool &removed)
{
    BTNode *current = root, *prev = nullptr;

    if (root == nullptr)
    {
        removed = false;
        return nullptr;
    }

    if (root->item == item)
    {
        if (root->left == nullptr && root->right == nullptr)
        {
            removed = true;
            root = nullptr;
        }
        else
        {
            removed = false;
        }
        return current;
    }
    while (current != nullptr && current->item != item)
    {
        prev = current;
        if (current->item < item)
            current = current->right;
        else if (current->item > item)
            current = current->left;
    }

    if (current == nullptr)
    {
        removed = false;
        return nullptr;
    }
    else
    {
        if (current->left == nullptr && current->right == nullptr)
        {
            removed = true;
            if (prev->left->item == item)
                prev->left = nullptr;
            else
                prev->right = nullptr;
        }
        else
        {
            removed = false;
        }
        return current;
    }
}