How to balance a random binary search tree with an array (in Java)?

Hi,

I got the following assignment - I have a certain java code for a binary search tree and I need to add methods to do the following things with it:

1. Transform the BST into an array that's sorted by BST data keys.
2. Create a balanced BST from an ordered integer array.
3. Use 1. and 2. to balance an existing BST (randomly generated and presumably somewhat unbalanced)
4. Display the BST before and after balancing.

Please guys, help me if you're smarter than me and know how can that be achieved!

Here is the code that I need to work with:

import java.util.*;
class BtreeNode {

int data;
BtreeNode L,R;
static int depth=0;

public BtreeNode(){
data = 0; L = null; R=null;
}
public BtreeNode(int key){
this();data = key;
}
public String toString() {
return "["+data+"]";
}

public static BtreeNode insOrd(BtreeNode roo, int key){
if(roo==null)return new BtreeNode(key);
//Не се допуска повторение на ключове
if(key==roo.data)return roo;
if(key<roo.data)roo.L=insOrd(roo.L,key);
else roo.R=insOrd(roo.R,key);
return roo;
}

public static BtreeNode generate(int length) {
BtreeNode start = null;
Random rn = new Random();
for(int i = 0; i < length; i++){
start = insOrd(start,rn.nextInt(10000));
}
return start;
}

public static void spc(int n){
for(int i=0;i<n;i++)System.out.print(" ");
}

public static void print(BtreeNode roo){
if(roo!=null){
depth++;
print(roo.R);
spc(depth);System.out.println(roo);
print(roo.L);
depth--;
}
}

public static BtreeNode find(BtreeNode roo, int key){
BtreeNode r=null;
if(roo==null)return r;
if(roo.data==key)r= roo;
if(key>roo.data)r= find(roo.R,key);
if(key<roo.data)r= find(roo.L,key);
return r;
}
};

public class Main {

public static void main(String[] args){
int N;
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number if tree items:");
N=sc.nextInt();
BtreeNode c = BtreeNode.generate(N);
BtreeNode.print(c);
/*
System.out.println("This tree has "+
BtreeNode.weight(c)+" nodes and "+
BtreeNode.height(c)+" levels.");
*/
}
}