Hello, I've been looking at this problem for a few hours, and I can't figure it out. We had to test this code and fix it if we find errors (it's a splay tree):

``````public class SplayBST {

Node root;
int count;
int level = 0;

public SplayBST() {
root = null;
count = 0;
}

//assumes no duplicates
root = splayInsert(root, x);
count++;
}

// moves node containing x to the root
public Node search(String x) {
System.out.println("Search");
return root = splaySearch(root, x);
}

Node splayInsert(Node h, String x) {
if (h == null) {
return new Node(x);
}
if (x.compareTo(h.value) < 0) {

if (h.left == null) {
h.left = new Node(x);
return rotateRight(h);
}

if (x.compareTo(h.left.value) < 0) {
h.left.left = splayInsert(h.left.left, x);

h = rotateRight(h);
} else {
h.left.right = splayInsert(h.left.right, x);
h.left = rotateLeft(h.left);
}
return rotateRight(h);

} else { //x.compareTo(h.value)>0
if (h.right == null) {

h.right = new Node(x);
return rotateLeft(h);
}

if (x.compareTo(h.right.value) > 0) {
h.right.right = splayInsert(h.right.right, x);

h = rotateLeft(h);
} else {
h.right.left = splayInsert(h.right.left, x);
h.right = rotateRight(h.right);
}
return rotateLeft(h);
}

}

Node splaySearch(Node h, String x) {
return h;
//tbd
}

Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
return x;
}

Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
return x;
}

void displayMe() {
String[][] output = new String[count * 2][count * 4];
output = putNode(1, (count * 4) / 2, root, output);

for (int i = 0; i < output.length; i++) {
String line = "";
for (int j = 0; j < output[i].length; j++) {

if (output[i][j] == null) {
output[i][j] = " ";
}
line += output[i][j];
}
System.out.println(line);
}

}

private String[][] putNode(int level, int pos, Node root, String[][] output) {
if (root == null) {
return output;
}
output[level][pos] = root.value;
if (root.left != null) {

output[level + 1][pos - 1] = "/";
}
if (root.right != null) {

output[level + 1][pos + 1] = "\\";
}
putNode(level + 2, pos - 2, root.left, output);
putNode(level + 2, pos + 2, root.right, output);

return output;
}

class Node {

Node left;
Node right;
String value;
int pos;

public Node(String x) {
left = null;
right = null;
value = x;
}
}
}``````

I managed to test it for a few cases:
These all provided correct output. However, adding 9,3,2,8,4,0 provided incorrect output, and I can't figure out why or how to fix it. Any hints are appreciated.

Thanks!