Answer to Question #268107 in C++ for Myname

Question #268107

Write a program to perform deletion operation on BST. While deleting, consider all the deletion cases.


a. Deletion of node with degree 0.


b. Deletion of node with degree 1.


c. Deletion of node with degree 2.

1
Expert's answer
2021-11-18T15:20:21-0500
#include <bits/stdc++.h>
using namespace std;


struct Node {
	int k;
	struct Node *lt, *rt;
};
Node* newNode(int it)
{
	Node* tp = new Node;
	tp->k = it;
	tp->lt = tp->rt = NULL;
	return tp;
}
void inorder(Node* r)
{
	if (r != NULL) {
		inorder(r->lt);
		printf("%d ", r->k);
		inorder(r->rt);
	}
}
Node* insert(Node* nd, int k)
{
	if (nd == NULL)
		return newNode(k);
	if (k < nd->k)
		nd->lt = insert(nd->lt, k);
	else
		nd->rt = insert(nd->rt, k);
	return nd;
}
Node* delete(Node* r, int n)
{
    if (r == NULL)
        return r;
    if (r->k > n) {
        r->left = delete(r->left, n);
        return r;
    }
    else if (r->k < n) {
        r->right = delete(r->right, n);
        return r;
    }
    if (r->left == NULL) {
        Node* temp = r->right;
        delete r;
        return temp;
    }
    else if (r->right == NULL) {
        Node* temp = r->left;
        delete r;
        return temp;
    }
    else {
 
        Node* succParent = r;
        Node* succ = r->right;
        while (succ->left != NULL) {
            succParent = succ;
            succ = succ->left;
        }
        if (succParent != r)
            succParent->left = succ->right;
        else
            succParent->right = succ->right;
        r->k = succ->k;
        delete succ;
        return r;
    }
}
int main()
{
	Node* r = NULL;
	r = insert(r, 40);
	r = insert(r, 20);
	r = insert(r, 10);


	printf("Inorder traversal\n");
	inorder(r);


	printf("\nDelete 40\n");
	r = delete(r, 20);
	printf("Inorder traversal\n");
	inorder(r);


	return 0;
}

Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS