Método de inserción en un árbol binario de búsqueda.

Cuando inserto nodos en el árbol binario y lo pruebo en el main imprimiéndolo en orden, el resultado siempre está equivocado. He probado otras soluciones pero solo han creado problemas mayores y en la salida, se muestra en el orden equivocado. Reviso la pantalla y es perfecto, pero el problema está en el método insert (inserta claves no repetidas).

“`class BSTNode {
public int key;
public T data;
public BSTNode<t> left, right;

public BSTNode(int k, T val) {
key = k;
data = val;
left = right = null;
}

public BSTNode(int k, T val, BSTNode<t> l, BSTNode<t> r) {
key = k;
data = val;
left = l;
right = r;
}
}

public class BST<t> {
BSTNode<t> root, current;

public BST() {
root = current = null;
}

public boolean empty() {
return root == null;
}

public boolean full() {
return false;
}

public T retrieve() {
return current.data;
}

public boolean findkey(int tkey) {
BSTNode<t> p = root, q = root;

<pre><code>if (empty())
return false;
int nb = 0;
while (p != null) {
q = p;
nb++;
if (p.key == tkey) {
current = p;
return true;
} else if (tkey < p.key)
p = p.left;
else
p = p.right;
}

current = q;
return false;
</code></pre>

}

public boolean insert(int key, T val) {
BSTNode<t> p = current, q = current;

<pre><code>while (p != null) {
q = p;
if (p.key == key) {
return false;
} else if (key < p.key)
p = p.left;
else
p = p.right;
}

p = new BSTNode<t>(key, val);
if (empty()) {
root = current = p;
return true;
} else {
// current apunta al padre de la nueva clave
if (key < current.key)
current.left = p;
else
current.right = p;
current = p;
return true;
}
</code></pre>

}

public void display() {
if (root == null)
System.out.println("EL ARBOL ESTA VACIO");
else
displayin(root);
System.out.println();
}

private void displayin(BSTNode<t> p) {
if (p != null) {
displayin(p.left);
System.out.print(p.key + " " + p.data + " , ");
displayin(p.right);
}
}
}“`