#include

using namespace std;

struct Node $\{$

int data;

Node $*$left;

Node $*$right;

$\}$;

Node $*$search$($Node $*$root$,$ int k$)\{$

if $($root $==$ NULL $||$ root$->$data $==$ k$)$

return root;

if $($root$->$data $$ k$)$

return search$($root$->$right, k$)$;

else

return search$($root$->$left, k$)$;

$\}$

Node $*$insert$($Node $*$node$,$ int k$)\{$

if $($node $==$ NULL$)\{$

Node $*$newNode $=$ new Node;

newNode$->$data $=$ k;

newNode$->$left $=$ NULL;

newNode$->$right $=$ NULL;

return newNode;

$\}$ else if $($k $>$ node$->$data$)$

node$->$right $=$ insert$($node$->$right, k$)$;

else

node$->$left $=$ insert$($node$->$left, k$)$;

return node;

$\}$

$//$ Find the inorder successor

Node $*$minValueNode$($Node $*$node$)\{$

Node $*$current $=$ node;

$//$ Find the leftmost leaf

while $($current $!=$ NULL && current$->$left $!=$ NULL$)$

current $=$ current$->$left;

return current;

$\}$

Node $*$maxValueNode$($Node $*$node$)\{$

Node $*$current $=$ node;

$//$ Find the rightmost leaf

while $($current $!=$ NULL && current$->$right $!=$ NULL$)$

current $=$ current$->$right;

return current;

$\}$

Node $*$deleteNode$($Node $*$root$,$ int k$)\{$

if $($root $==$ NULL$)$

return root;

if $($k $$ root$->$data$)$

root$->$left $=$ deleteNode$($root$->$left, k$)$;

else if $($k $>$ root$->$data$)$

root$->$right $=$ deleteNode$($root$->$right, k$)$;

else $\{$

if $($root$->$left $==$ NULL$)\{$

Node $*$temp $=$ root$->$right;

delete root;

return temp;

$\}$ else if $($root$->$right $==$ NULL$)\{$

Node $*$temp $=$ root$->$left;

delete root;

return temp;

$\}$

Node $*$temp $=$ minValueNode$($root$->$right$)$;

root$->$data $=$ temp$->$data;

root$->$right $=$ deleteNode$($root$->$right, temp$->$data$)$;

$\}$

return root;

$\}$

void inorder$($Node $*$n$)\{$

if $($n $!=$ NULL$)\{$

inorder$($n$->$left$)$;

cout $$ n$->$data ;

inorder$($n$->$right$)$;

$\}$

$\}$

void preorder$($Node $*$n$)\{$

if $($n $!=$ NULL$)\{$

cout $$ n$->$data ;

preorder$($n$->$left$)$;

preorder$($n$->$right$)$;

$\}$

$\}$

void postorder$($Node $*$n$)\{$

if $($n $!=$ NULL$)\{$

postorder$($n$->$left$)$;

postorder$($n$->$right$)$;

cout $$ n$->$data ;

$\}$

$\}$

int main$()\{$

Node $*$root $=$ NULL;

root $=$ insert$($root$,30)$;

insert$($root$,40)$;

insert$($root$,20)$;

insert$($root$,100)$;

insert$($root$,10)$;

insert$($root$,5)$;

inorder$($root$)$;

cout $$ endl;

Node $*$searchresult $=$ search$($root$,0)$;

if $($searchresult $==$ NULL$)$

cout $$ "the value is not found" $$ endl;

else

cout $$ "the value is found" $$ endl;

root $=$ deleteNode$($root$,5)$;

inorder$($root$)$;

cout $$ endl;

root $=$ deleteNode$($root$,20)$;

inorder$($root$)$;

cout $$ endl;

root $=$ deleteNode$($root$,30)$;

inorder$($root$)$;

cout $$ endl;

return $0$;

$\}$ using the following code solve this Q