# (Invalid) Bug: A (in)valid O(n) solution is not accepted by the judge

• [Update] The following is invalid because I didn't notice that the three has to be "height balanced" which means that for each node the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1. Thanks Stefan for pointing this out.

This is what I get from the judge when submitting one of the solutions. It is a valid solution, but the judge doesn't accept it. Is there a way to file a bug report?

``````Input:
[-1,0,1,2]
Output:
[2,0,null,-1,1]
Expected:
[1,0,2,-1]
``````

The O(n) java solution that causes the bug:

``````public class Solution {
private static class State {
}
}
}
private TreeNode sortedListToBST(int limit, State state) {
if (limit == 0 || state.head == null) return null;
int depth = 1;
limit--;
while (state.head != null && limit > 0) {
newRoot.left = root;
root = newRoot;
limit--;
int rightLimit = (int)Math.pow(2,depth) - 1;
root.right = sortedListToBST(rightLimit, state);
limit -= rightLimit;
depth++;
}
return root;
}
}``````

• [2,0,null,-1,1] is not acceptable. The root's left subtree is two levels higher than its right subtree.

• Thanks for pointing this out. I've updated the post to say that this is an invalid bug.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.