dev/bst_tries_02.cpp
struct node* TreeDeleteNode(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 = TreeDeleteNode(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 = TreeDeleteNode(root->right, key); 

	// if key is same as root's key, then This is the node 
	// to be deleted 
	else
	{ 
		// node with only one child or no child 
		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 = TreeDeleteNode(root->right, temp->key); 
	} 
	return root; 
}
/* Given a binary search tree and a key, this function deletes the key 
and returns the new root */
Given a binary search tree and a key, this function deletes the key
and returns the new root
Given a binary search tree and a key this function deletes the key and returns the new root
struct node* TreeDeleteNode(struct node* root, int key) 
{ 
	if (root == NULL) return root; 
	if (key < root->key) 
		root->left = TreeDeleteNode(root->left, key); 
	else if (key > root->key) 
		root->right = TreeDeleteNode(root->right, key); 
	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; 
		} 
		struct node* temp = minValueNode(root->right); 
		root->key = temp->key; 
		root->right = TreeDeleteNode(root->right, temp->key); 
	} 
	return root; 
}
struct node * TreeDeleteNode ( struct node * root , int key ) { if ( root == NULL ) return root ; if ( key < root -> key ) root -> left = TreeDeleteNode ( root -> left , key ) ; else if ( key > root -> key ) root -> right = TreeDeleteNode ( root -> right , key ) ; 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 ; } struct node * temp = minValueNode ( root -> right ) ; root -> key = temp -> key ; root -> right = TreeDeleteNode ( root -> right , temp -> key ) ; } return root ; }
Given a binary search tree and a key, this function deletes the key
and returns the new root
Given a binary search tree and a key this function deletes the key and returns the new root
// base case  // If the key to be deleted is smaller than the root's key,  // then it lies in left subtree  // If the key to be deleted is greater than the root's key,  // then it lies in right subtree  // if key is same as root's key, then This is the node  // to be deleted  // node with only one child or no child  // node with two children: Get the inorder successor (smallest  // in the right subtree)  // Copy the inorder successor's content to this node  // Delete the inorder successor 