Hi$!$ I need help implimenting a balance$()$ method that balances a existing BST$.$ There is more information in the photo attached and here is the code i have so far:

public void balance$()$

$\{$

LinkedList nodes $=$ new LinkedList;

sortNodes$($nodes$,$ root$)$;

root $=$ balanceTree$($nodes$,0,$ size$()-1)$;

$\}$

private void sortNodes$($LinkedList nodes, Node n$)$

$\{$

if$($n $==$ null$)$

$\{$

return;

$\}$

sortNodes$($nodes$,$ n$.$left$)$;

nodes.add$($n$)$;

sortNodes$($nodes$,$ n$.$right$)$;

$\}$

private Node balanceTree$($LinkedList nodes, int start, int end$)$

$\{$

if$($start $>$ end$)$

$\{$

return null;

$\}$

int middle $=($start $+$ end$)/2$;

if$(($start $+$ end$)\%2==1)$

$\{$

middle$++$;

$\}$

Node middleNode $=$ nodes.get$($middle$)$;

middleNode.left $=$ balanceTree$($nodes$,$ start,middle$-1)$;

middleNode.right $=$ balanceTree$($nodes$,$ middle $+1,$ end$)$;

return middleNode;

$\}$

It is not working correctly on some of the tests:

$8\mathrm{.}3)$ balance$()3[$Hint: Balances short left stilted tree and updates node sizes.$](0/2\mathrm{.}5)$ Test Failed!

Node $($key:$4)$ does not have correct N value, expected $4$ found $3.$

at edu.ser$222.$m$03\_02.$tests.BSTTest.assertNodeNValues:$425($BSTTest$.$java$)$

at edu.ser$222.$m$03\_02.$tests.BSTTest.testBalance$3$:$414($BSTTest$.$java$)$

$8\mathrm{.}4)$ balance$()4[$Hint: Balances short right stilted tree and updates node sizes.$](0/2\mathrm{.}5)$ Test Failed!

Node $($key:$5)$ does not have correct N value, expected $5$ found $3.$

at edu.ser$222.$m$03\_02.$tests.BSTTest.assertNodeNValues:$425($BSTTest$.$java$)$

at edu.ser$222.$m$03\_02.$tests.BSTTest.testBalance$4$:$447($BSTTest$.$java$)$

$8\mathrm{.}5)$ balance$()5[$Hint: Balances right stilted tree and updates node sizes.$](0/3)$ Test Failed!

Node $($key:$6)$ does not have correct N value, expected $6$ found $3.$

at edu.ser$222.$m$03\_02.$tests.BSTTest.assertNodeNValues:$425($BSTTest$.$java$)$

at edu.ser$222.$m$03\_02.$tests.BSTTest.testBalance$5$:$471($BSTTest$.$java$)$