#include

using namespace std;

struct Node $\{$

int data;

Node $*$left;

Node $*$right;

$\}$;

const int MAXSIZE $=10$;

Node $*$queue$[$MAXSIZE$]$;

int front $=-1,$ rear $=-1$;

void resetQueue$()\{$

rear $=-1$;

front $=-1$;

$\}$

bool queueIsEmpty$()\{$

if $($front $<mtext\; id="EditorElement\_15688995"></mtext><mn\; id="EditorElement\_15688996">0</mn><mi\; id="EditorElement\_15688997">)</mi>$

return true;

else

return false;

$\}$

bool queueIsFull$()\{$

if $(($rear $+1)\%$ MAXSIZE $==$ front$)$

return true;

else

return false;

$\}$

Node $*$peek$()\{$ return queue$[$front$]$; $\}$

void printQueue$()\{$

if $(!$queueIsEmpty$())\{$

int i $=0$;

for $($i $=$ front; i $!=$ rear;$)\{$

cout $$ queue$[$i$]->$data ;

i $=($i $+1)\%$ MAXSIZE;

$\}$

cout $$ queue$[$i$]->$data ;

cout $$ endl;

$\}$

$\}$

void enqueue$($Node $*$data$)\{$

if $(!$queueIsFull$())\{$

if $($front $==-1)\{$

front $=0$;

rear $=0$;

$\}$ else

rear $=($rear $+1)\%$ MAXSIZE;

queue$[$rear$]=$ data;

$\}$ else

cout $$ "Queue is full" $$ endl;

$\}$

Node $*$dequeue$()\{$

Node $*$data $=$ queue$[$front$]$;

if $($front $==$ rear$)\{$

rear $=-1$;

front $=-1$;

$\}$ else

front $=($front $+1)\%$ MAXSIZE;

return data;

$\}$

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

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

cout $$ n$->$data ;

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

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

$\}$

$\}$

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

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

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

cout $$ n$->$data ;

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

$\}$

$\}$

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

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

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

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

cout $$ n$->$data ;

$\}$

$\}$

void level$\_$order$($Node $*$n$)\{$

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

enqueue$($n$)$;

while $(!$queueIsEmpty$())\{$

Node $*$temp $=$ dequeue$()$;

cout $$ temp$->$data ;

if $($temp$->$left $!=$ NULL$)$

enqueue$($temp$->$left$)$;

if $($temp$->$right $!=$ NULL$)$

enqueue$($temp$->$right$)$;

$\}$

$\}$

$\}$

Node $*$insert$($Node $*$n$,$ int x$)\{$

Node $*$newNode $=$ new Node;

newNode$->$data $=$ x;

newNode$->$left $=$ NULL;

newNode$->$right $=$ NULL;

if $($n $==$ NULL$)$

n $=$ newNode;

else $\{$

enqueue$($n$)$;

while $(!$queueIsEmpty$())\{$

Node $*$temp $=$ dequeue$()$;

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

temp$->$left $=$ newNode;

break;

$\}$ else

enqueue$($temp$->$left$)$;

if $($temp$->$right $==$ NULL$)\{$

temp$->$right $=$ newNode;

break;

$\}$ else

enqueue$($temp$->$right$)$;

$\}$

$\}$

return n;

$\}$

Node $*$deleteTreeDeepestRightMostNode$($Node $*$n$,$ Node $*$targetNode$)\{$

enqueue$($n$)$;

while $(!$queueIsEmpty$())\{$

Node $*$temp $=$ dequeue$()$;

if $($temp $==$ targetNode$)\{//$ when targed node is the root node

delete temp;

return NULL;

$\}$

if $($temp$->$left $!=$ NULL && temp$->$left $!=$ targetNode$)$

enqueue$($temp$->$left$)$;

else $\{$

if $($temp$->$left $!=$ NULL$)\{$

delete temp$->$left;

temp$->$left $=$ NULL;

return n;

$\}$

$\}$

if $($temp$->$right $!=$ NULL && temp$->$right $!=$ targetNode$)$

enqueue$($temp$->$right$)$;

else $\{$

if $($temp$->$right $!=$ NULL$)\{$

delete temp$->$right;

temp$->$right $=$ NULL;

return n;

$\}$

$\}$

$\}$

return n;

$\}$

Node $*$deleteTreeNode$($Node $*$n$,$ int x$)\{$

enqueue$($n$)$;

Node $*$tobedeleted;

Node $*$deepestRightMostNode;

while $(!$queueIsEmpty$())\{$

Node $*$temp $=$ dequeue$()$;

deepestRightMostNode $=$ temp;

if $($temp$->$data $==$ x$)$

tobedeleted $=$ temp;

if $($temp$->$left $!=$ NULL$)$

enqueue$($temp$->$left$)$;

if $($temp$->$right $!=$ NULL$)$

enqueue$($temp$->$right$)$;

$\}$

resetQueue$()$;

tobedeleted$->$data $=$ deepestRightMostNode$->$data;

n $=$ deleteTreeDeepestRightMostNode$($n$,$ deepestRightMostNode$)$;

return n;

$\}$

int main$()\{$

Node $*$root $=$ NULL;

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

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

resetQueue$()$;

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

resetQueue$()$;

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

resetQueue$()$;

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

resetQueue$()$;

preorder$($root$)$;

cout $$ endl;

inorder$($root$)$;

cout $$ endl;

postorder$($root$)$;

cout $$ endl;

level$\_$order$($root$)$;

resetQueue$()$;

cout $$ endl;

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

resetQueue$()$;

level$\_$order$($root$)$;

resetQueue$()$;

root $=$ deleteTreeNode$($root$,2)$;

resetQueue$()$;

cout $$ endl;

level$\_$order$($root$)$;

resetQueue$()$;

cout $$ endl;

return $0$;

$\}$