C++ program to remove all leaf nodes from the binary search tree














































C++ program to remove all leaf nodes from the binary search tree



#include<iostream> /* 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