I need help with the to do part in the picture, question is mentioned below. Thank you so much for the answer.

In this question, you have to perform add on AVL tree. Note that:

$-$ When adding a node which has the same value as parent node, add it in the right sub tree.

Your task is to implement function: insert. You could define one or more functions to achieve this task.

#include

#include

#include

using namespace std;

#define SEPARATOR $"$##$"$

enum BalanceValue

$\{$

LH $=-1,$

EH $=0,$

RH $=1$

$\}$;

void printNSpace$($int n$)$

$\{$

for $($int i $=0$; i $$ n $-1$; i$++)$

cout ;

$\}$

void printInteger$($int &n$)$

$\{$

cout $$ n ;

$\}$

template

class AVLTree

$\{$

public:

class Node;

private:

Node $*$root;

protected:

int getHeightRec$($Node $*$node$)$

$\{$

if $($node $==$ NULL$)$

return $0$;

int lh $=$ this$->$getHeightRec$($node$->$pLeft$)$;

int rh $=$ this$->$getHeightRec$($node$->$pRight$)$;

return $($lh $>$ rh $?$ lh : rh$)+1$;

$\}$

public:

AVLTree$()$ : root$($nullptr$)\{\}$

~AVLTree$()\{\}$

int getHeight$()$

$\{$

return this$->$getHeightRec$($this$->$root$)$;

$\}$

void printTreeStructure$()$

$\{$

int height $=$ this$->$getHeight$()$;

if $($this$->$root $==$ NULL$)$

$\{$

cout $$ "NULL

$"$;

return;

$\}$

queue q;

q$.$push$($root$)$;

Node $*$temp;

int count $=0$;

int maxNode $=1$;

int level $=0$;

int space $=$ pow$(2,$ height$)$;

printNSpace$($space $/2)$;

while $(!$q$.$empty$())$

$\{$

temp $=$ q$.$front$()$;

q$.$pop$()$;

if $($temp $==$ NULL$)$

$\{$

cout ;

q$.$push$($NULL$)$;

q$.$push$($NULL$)$;

$\}$

else

$\{$

cout $$ temp$->$data;

q$.$push$($temp$->$pLeft$)$;

q$.$push$($temp$->$pRight$)$;

$\}$

printNSpace$($space$)$;

count$++$;

if $($count $==$ maxNode$)$

$\{$

cout $$ endl;

count $=0$;

maxNode $*=2$;

level$++$;

space $/=2$;

printNSpace$($space $/2)$;

$\}$

if $($level $==$ height$)$

return;

$\}$

$\}$

void insert$($const T &value$)$

$\{$

$//$TODO

$\}$

class Node

$\{$

private:

T data;

Node $*$pLeft$,*$pRight;

BalanceValue balance;

friend class AVLTree;

public:

Node$($T value$)$ : data$($value$),$ pLeft$($NULL$),$ pRight$($NULL$),$ balance$($EH$)\{\}$

~Node$()\{\}$

$\}$;

$\}$;

$\}$