Answer to Question #270735 in C++ for somu

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* r1 = NULL;
	r1 = insert(r1, 50);
	r1 = insert(r1, 40);
	r1 = insert(r1, 30);




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




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




	return 0;
}