deletion in binary trees

Delete 10 in below tree

Output :    
  


Delete 20 in below tree

Output :    

While performing the delete operation on binary trees, there arise a few cases:

1)The node to be deleted is a leaf node. That is it does not have any children.

2)The node to be deleted is a internal node. That is it have left or right child.

3)The node to be deleted is the root node.

In the first case 1, since the node to be deleted is a leaf node, we can simply delete the node without any overheads. But in the next 2 cases, we will have to take care of the children of the node to be deleted.

In order to handle all of the cases, one way to delete a node is to:

Starting at the root, find the deepest and rightmost node in binary tree and node which we want to delete.

Replace the deepest rightmost node’s data with the node to be deleted.

Then delete the deepest rightmost node.

                               

c++:

// Function to delete the given deepest node 
// (d_node) in binary tree 
void deletDeepest(struct Node *root, struct Node *d_node) 
{ 
    queue<struct Node*> q; 
    q.push(root); 

    // Do level order traversal until last node 
    struct Node* temp; 
    while(!q.empty()) 
    { 
        temp = q.front(); 
        q.pop(); 

        if (temp->right) 
        { 
            if (temp->right == d_node) 
            { 
                temp->right = NULL; 
                delete(d_node); 
                return; 
            } 
            else
                q.push(temp->right); 
        } 

        if (temp->left) 
        { 
            if (temp->left == d_node) 
            { 
                temp->left=NULL; 
                delete(d_node); 
                return; 
            } 
            else
                q.push(temp->left); 
        } 
    } 
} 

// Function to delete element in binary tree 
void deletion(struct Node* root, int key) 
{ 
    queue<struct Node*> q; 
    q.push(root); 

    struct Node *temp; 
    struct Node *key_node = NULL; 

    // Do level order traversal to find deepest 
    // node(temp) and node to be deleted (key_node) 
    while (!q.empty()) 
    { 
        temp = q.front(); 
        q.pop(); 

        if (temp->key == key) 
            key_node = temp; 

        if (temp->left) 
            q.push(temp->left); 

        if (temp->right) 
            q.push(temp->right); 
    } 

    int x = temp->key; 
    deletDeepest(root, temp); 
    key_node->key = x; 
} 

java:

  // Function to delete the given deepest node 
    // (d_node) in binary tree 
    static void deleteDeepest(Node root, Node d_node) 
    {
        Queue<Node> q = new LinkedList<Node>(); 
        q.add(root); 
    
        // Do level order traversal until last node 
        Node temp; 
        while(!q.isEmpty()) 
        { 
            temp = q.peek(); 
            q.remove(); 
    
            if (temp.right!=null) 
            { 
                if (temp.right == d_node) 
                { 
                    temp.right = null; 
                    d_node = null; 
                    return; 
                } 
                else
                    q.add(temp.right); 
            } 
    
            if (temp.left!=null) 
            { 
                if (temp.left == d_node) 
                { 
                    temp.left=null; 
                    d_node = null; 
                    return; 
                } 
                else
                    q.add(temp.left); 
            } 
        } 
    } 
    
    // Function to delete element in binary tree 
    static void deletion(Node root, int key) 
    { 
        Queue<Node> q = new LinkedList<Node>(); 
        q.add(root); 
    
        Node temp = null; 
        Node key_node = null; 
    
        // Do level order traversal to find deepest 
        // node(temp) and node to be deleted (key_node) 
        while (!q.isEmpty()) 
        { 
            temp = q.peek(); 
            q.remove(); 
    
            if (temp.key == key) 
                key_node = temp; 
    
            if (temp.left!=null) 
                q.add(temp.left); 
    
            if (temp.right!=null) 
                q.add(temp.right); 
        } 
    
        int x = temp.key; 
        deleteDeepest(root, temp); 
        key_node.key = x; 
    }