C++ program to remove all leaf nodes from the binary search tree
/*
Key points:
* Binary Search Tree or BST is the data structure that provides fast lookup/deletion/inserting in logarithmic complexity
* In BST, every node has a key value associated with them.
* In BST, key of the left subtree < key of the root < key of the right subtree
* In-order traversal of BST produces the sorted order of keys
Assumptions:
* We assumed that all the keys will be unique in BST.
*/
template<typename T>
struct Data{
T data; // Key of node
Data(){
data = 0; // default key of node
}
};
template<typename T>
struct Node{
Data<T> key;
Node<T> *left,*right;
Node(){ // constructor
left = right = nullptr;
}
};
template<typename T>
Node<T>* CreateNode(T value){ // Function to create Node
Node<T>* node = new Node<T>;
node->key.data = value;
return node;
}
template<typename T>
Node<T>* InsertNode(Node<T>* root, T value){ // Function to insert a node
if(root == nullptr){ // Nothing in current tree make new node
return CreateNode<T>(value);
}
if(root->key.data > value){ // key is lesser than node's key, insert in left subtree
root->left = InsertNode<T>(root->left,value);
}
if(root->key.data < value){ // ket is greater than node's key, insert in right subtree
root->right = InsertNode<T>(root->right,value);
}
return root;
}
template<typename T>
Node<T>* DeleteLeafNodes(Node<T>* root){ // Function to delete Leaf nodes
if(root->left == nullptr && root->right == nullptr){ // delete this leaf Node and free memory
free(root);
return nullptr;
}
if(root->left != nullptr)root->left = DeleteLeafNodes<T>(root->left); // recursively delete leaf of left subtree
if(root->right != nullptr)root->right = DeleteLeafNodes<T>(root->right); // recursively delete leaf of right subtree
return root;
}
template<typename T>
void inorder(Node<T>* root){
if(root!=nullptr){
inorder(root->left);
std::cout << root->key.data << ' ';
inorder(root->right);
}
}
int main(){
/* Initial BST.
root-> (10)
/ \
/ \
(5) (20)
\ \
\ \
(9) (90)
/
/
(40)
After deletion of leaf 9,40
root-> (10)
/ \
/ \
(5) (20)
\
\
(90)
*/
Node<int> *root = nullptr;
root = InsertNode(root,10);
root = InsertNode(root,20);
root = InsertNode(root,5);
root = InsertNode(root,9);
root = InsertNode(root,90);
root = InsertNode(root,40);
std::cout << "Before deleting In-order of BST: ";
inorder(root);
root = DeleteLeafNodes(root);
std::cout << "\nAfter deleting In-order of BST: ";
inorder(root);
return 0;
}
/* Output:
Before deleting In-order of BST: 5 9 10 20 40 90
After deleting In-order of BST: 5 10 20 90
*/
Comments