using namespace std;
#include <iostream>
class Node {
public:
int key;
Node* left_child = NULL;
Node* right_child = NULL;
Node(int k) {
key = k;
}
Node() {}
};
/*
insert takes a key (value) and a parent (initially the root, changes when
executing the recursive function, though). It checks whether the key is
less than or greater than each parent node starting from the root until it
finds its place.
*/
Node* insert(int key, Node* parent) {
if (parent == NULL) {
return new Node(key);
}
if (key < parent->key) {
parent->left_child = insert(key, parent->left_child);
}
if (key > parent->key) {
parent->right_child = insert(key, parent->right_child);
}
return parent;
}
/*
deleteLeaf can find and delete a leaf node. If no leaf node is found with the specified key, then it returns false and does nothing else.
*/
bool deleteLeaf(int key, Node* parent) {
if (key == parent->key) {
return true;
}
else {
return false;
}
if (key < parent->key) {
bool found = deleteLeaf(key, parent->left_child);
if (found == true) {
parent->left_child = NULL;
parent->right_child = NULL;
}
}
else if (key > parent->key) {
bool found = deleteLeaf(key, parent->right_child);
if (found == true) {
parent->left_child = NULL;
parent->right_child = NULL;
}
}
return false;
}
void inorderTraversal(Node* n)
{
if (n == NULL)
return;
inorderTraversal(n->left_child);
cout << n->key << ", ";
inorderTraversal(n->right_child);
}
int main() {
Node* root = new Node(5);
insert(4, root);
insert(7, root);
insert(1, root);
insert(6, root);
insert(8, root);
cout << "\nInorder Traversal after insertions:\n";
inorderTraversal(root);
deleteLeaf(1, root);
cout << "\nAfter deletion of the node with the key value of 1 (leaf node):\n";
inorderTraversal(root);
}
