height$()$

Returns the height of the tree $($empty tree has height of $0).$

Must run in O$(1)$ time.

$*/$

int height$()$ const

$\{$

throw not$\_$implemented$\{\}$;

$\}$

$/*$ empty$()$

Returns true if the tree is empty.

Must run in O$(1)$ time.

$*/$

bool empty$()$ const

$\{$

throw not$\_$implemented$\{\}$;

$\}$

$/*$ find$($x$)$

Returns a pointer to the node containing $`$x$`,$ or nullptr if $`$x$`$ is not

found in the tree.

Must run in O$($log n$)$ time.

NOTE: If you want to write $`$find$`$ recursively, you'll need to add a

private helper function

node$*$ find$($node$*$ n$,$ int x$)$;

to do the actual recursion.

$*/$

node$*$ find$($int x$)$

$\{$

throw not$\_$implemented$\{\}$;

$\}$

$/*$ insert$($x$)$

Insert $`$x$`$ into the tree. If $`$x$`$ already exists in the tree, then the

tree should be left unchanged. Otherwise, if $`$x$`$ is added to the tree,

then the tree should be rebalanced as necessary, so that the AVL height

property still holds.

Must run in O$($log n$)$ time.

$*/$

void insert$($int x$)$

$\{$

throw not$\_$implemented$\{\}$;

$\}$

$/*$ size$($n$)$

Returns the size of the tree under the node $`$n$`,$ using recursion. This

is the $($recursive$)$ implementation of the $`$size$()`$ method, above.

Must run in O$($n$)$ time. Note that because you are not allowed to add

additional private data members, you cannot use the $`$int sz;$`$ trick to

make this O$(1).$

$*/$

static int size$($node$*$ root$)$

$\{$

throw not$\_$implemented$\{\}$;

$\}$

$/*$ destroy$($root$)$

Destroy $`$root$`$ and all its descendants.

Must run in O$($n$)$ time, where

n $=$ size$($root$)$

This is called from the destructor to destroy the tree.

$*/$

static void destroy$($node$*$ root$)$

$\{$

$//$ Your code here.

$\}$

$/*$ copy$($root$,$ parent$)$

Return a copy of the tree under $`$root$`,$ with root's parent

being $`$parent$`.$

Must run in O$($n$)$ time.

$*/$

static node$*$ copy$($node$*$ root, node$*$ parent $=$ nullptr$)$

$\{$

$//$ Your code here.

return nullptr;

$\}$

I have an AVL tree class and am not sure how to proceed with the following functions