CPP

bst deleting

'''
        inorder()function time complexity   : O(n)
        insert() function time complexity   : O(n)
        delete() function time complexity   : O(n)
'''

# Python program to delete operation
# in binary search tree(BST)

# A Binary Tree Node
class Node:

    # Constructor to create a new node
    def __init__(self, key):
        self.val = key
        self.left = None
        self.right = None


# A function to do inorder traversal
def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.val, end=' ')
        inorder(root.right)


# A function to insert a new node
def insert(root, key):
    # if the tree is empty, return a new node
    if root is None:
        return Node(key)

    # otherwise recur down the tree
    if root.val < key:
        root.right = insert(root.right, key)
    else:
        root.left = insert(root.left, key)

    return root


# A function min key value found in that tree
def minValueNode(root):
    while root.left is not None:
        root = root.left

    return root


# Given a binary search tree and a key, this function
# delete the key and returns the new root
def deleteNode(root, key):
    # Base case
    if root is None:
        return root

    # if the key to be deleted is smaller than the root's
    # key then it lies in left subtree
    if root.val > key:
        root.left = deleteNode(root.left, key)

    # if the key to be delete is greater then the root's key
    # then it lies in right subtree
    elif root.val < key:
        root.right = deleteNode(root.right, key)

    else:

        # Node with only child or no child
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        # Node with two children Get teh inorder successor
        # smallest in the right subtree
        temp = minValueNode(root.right)

        # Copy the inorder successor's content to this node
        root.val = temp.val

        # Delete the inorder successor
        root.right = deleteNode(root.right, temp.val)

    return root


# Driver program to test above functions
if __name__ == '__main__':
    """ Let us create following BST 
                  50 
               /      
              30      70 
             /      /   
           20   40  60   80
                   /   
                  55
    inorder traversal->[20, 30, 40, 50, 55, 60, 70, 80]
    """
    root = None
    root = insert(root, 80)
    root = insert(root, 50)
    root = insert(root, 30)
    root = insert(root, 55)
    root = insert(root, 20)
    root = insert(root, 40)
    root = insert(root, 70)
    root = insert(root, 60)

    print("Inorder traversal of the given tree")
    inorder(root)

    print("

Delete->50")
    root = deleteNode(root, 50)
    print("Inorder traversal of the modified tree")
    inorder(root)

    print("

Delete->20")
    root = deleteNode(root, 20)
    print("Inorder traversal of the modified tree")
    inorder(root)

    print("

Delete->30")
    root = deleteNode(root, 70)
    print("Inorder traversal of the modified tree")
    inorder(root)

remove in bst

struct Node{
    Node *left, *right;
    int val;
    Node(int data){
        val=data;
        left=right=NULL;
    }
};

Node* inordersuccessor(Node* root){
    Node* curr=root;
    while(curr!=NULL && curr->left!=NULL){
        curr=curr->left;
    }
    return curr;
}

Node* remove(Node* root, int x){
    if(root==NULL) return root;
    else if(x<root->val){
        root->left=remove(root->left,x);
    }
    else if(x>root->val){
        root->right=remove(root->right,x);
    }
    else{
        if(root->left==NULL){
            Node* temp=root->right;
            delete(root);
            return temp;
        }
        else if(root->right==NULL){
            Node* temp=root->left;
            delete(root);
            return temp;
        }
        else{
            Node* ins=inordersuccessor(root->right);
            root->val=ins->val;
            root->right=remove(root->right,ins->val);
        }
        
    }
    return root;
}

deletion in bst

// C++ program to demonstrate 
// delete operation in binary
// search tree
#include <bits/stdc++.h>
using namespace std;

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

// A utility function to create a new BST node
struct node* newNode(int item)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A utility function to do 
// inorder traversal of BST
void inorder(struct node* root)
{
    if (root != NULL) {
        inorder(root->left);
        cout << root->key;
        inorder(root->right);
    }
}

/* A utility function to 
insert a new node with given key in
 * BST */
struct node* insert(struct node* node, int key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL)
        return newNode(key);

    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    /* return the (unchanged) node pointer */
    return node;
}

/* Given a non-empty binary search tree, return the node
with minimum key value found in that tree. Note that the
entire tree does not need to be searched. */
struct node* minValueNode(struct node* node)
{
    struct node* current = node;

    /* loop down to find the leftmost leaf */
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

/* Given a binary search tree and a key, this function
deletes the key and returns the new root */
struct node* deleteNode(struct node* root, int key)
{
    // base case
    if (root == NULL)
        return root;

    // If the key to be deleted is 
    // smaller than the root's
    // key, then it lies in left subtree
    if (key < root->key)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted is
    // greater than the root's
    // key, then it lies in right subtree
    else if (key > root->key)
        root->right = deleteNode(root->right, key);

    // if key is same as root's key, then This is the node
    // to be deleted
    else {
        // node has no child
        if (root->left==NULL and root->right==NULL)
            return NULL;
      
        // node with only one child or no child
        else if (root->left == NULL) {
            struct node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct node* temp = root->left;
            free(root);
            return temp;
        }

        // node with two children: Get the inorder successor
        // (smallest in the right subtree)
        struct node* temp = minValueNode(root->right);

        // Copy the inorder successor's content to this node
        root->key = temp->key;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

// Driver Code
int main()
{
    /* Let us create following BST
            50
        /     
        30     70
        /  / 
    20 40 60 80 */
    struct node* root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    cout << "Inorder traversal of the given tree 
";
    inorder(root);

    cout << "
Delete 20
";
    root = deleteNode(root, 20);
    cout << "Inorder traversal of the modified tree 
";
    inorder(root);

    cout << "
Delete 30
";
    root = deleteNode(root, 30);
    cout << "Inorder traversal of the modified tree 
";
    inorder(root);

    cout << "
Delete 50
";
    root = deleteNode(root, 50);
    cout << "Inorder traversal of the modified tree 
";
    inorder(root);

    return 0;
}

// This code is contributed by shivanisinghss2110