Answer to Question #268107 in C++ for Myname

Question

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.

Answer 1

#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;
}