#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int val) : data(val), left(NULL), right(NULL) {}
};
class BST {
public:
Node* root;
BST() { root = NULL; }
Node* insert(Node* node, int val) {
if (!node) return new Node(val);
if (val < node->data) node->left = insert(node->left, val);
else if (val > node->data) node->right = insert(node->right, val);
return node;
}
Node* remove(Node* node, int val) {
if (!node) return node;
if (val < node->data) node->left = remove(node->left, val);
else if (val > node->data) node->right = remove(node->right, val);
else {
if (!node->left) { Node* temp = node->right; delete node; return temp; }
if (!node->right) { Node* temp = node->left; delete node; return temp; }
Node* temp = minValueNode(node->right);
node->data = temp->data;
node->right = remove(node->right, temp->data);
}
return node;
}
Node* minValueNode(Node* node) {
Node* current = node;
while (current && current->left) current = current->left;
return current;
}
void inorder(Node* node) {
if (node) {
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
}
};
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
class BinarySearchTree {
Node root;
Node deleteRecursive(Node root, int key) {
if (root == null) return root;
if (key < root.data) root.left = deleteRecursive(root.left, key);
else if (key > root.data) root.right = deleteRecursive(root.right, key);
else {
if (root.left == null) return root.right;
else if (root.right == null) return root.left;
root.data = minValue(root.right);
root.right = deleteRecursive(root.right, root.data);
}
return root;
}
int minValue(Node root) {
int minv = root.data;
while (root.left != null) { minv = root.left.data; root = root.left; }
return minv;
}
}
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key
def deleteNode(root, key):
if root is None: return root
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
if root.left is None: return root.right
elif root.right is None: return root.left
temp = minValueNode(root.right)
root.val = temp.val
root.right = deleteNode(root.right, temp.val)
return root