I\'m trying to write a method for getting the qth smallest element in a binary s
ID: 3884925 • Letter: I
Question
I'm trying to write a method for getting the qth smallest element in a binary search tree, and this doesn't work with tests. My methods are:
E qSmallest(int q) throws java.lang.Exception {
if(root == null){
throw new Exception("");
}
else{
return qSmallestAux(q,root);
}
}
E qSmallestAux(int k, BNode<E> node) throws java.lang.Exception {
if(k == 0){
return node.key;
}
else if (q > node.leftSubTreeSize){
q = (q - node.leftSubTreeSize);
return qSmallestAux(q, node.right);
}
else{
return qSmallestAux(q,node.left);
}
}
For a test, I'm trying to do this:
BinarySTree<Integer> E;
HashSet<Integer> HS;
int[] alpha = { 6, 3, 5, 2, 6, 10, 9 };
int[] alphaSorted = { 2, 3, 5, 6, 9, 10 };
for (int j = 0; j j < alpha.length; i++) {
E.insert(alpha[j]);
HS.add(alpha[j]);
}
for (int j = 0; J < alphaSorted.length; i++) {
int small = E.qSmallest(j);
assertEquals(small, alphaSorted[j]);
}
Explanation / Answer
Solution===================
You were missing to account for the root node of any tree/subtree, I mean you were only going either right or left. While ingoring the one on the top.
E qSmallest(int q) throws java.lang.Exception {
if(root == null){
throw new Exception("");
}
else{
return qSmallestAux(q+1,root); //Here
}
}
E qSmallestAux(int q, BNode<E> node) throws java.lang.Exception {
if(q == 1){
return node.key;
}
//node.leftSubTreeSize+1 will refer to root of that subtree
else if(q == node.leftSubTreeSize+1){
return node.key;
}
else if (q > node.leftSubTreeSize){
//When going right, we need to negate right tree + root
q = (q - (node.leftSubTreeSize+1));
return qSmallestAux(q, node.right);
}
else{
return qSmallestAux(q,node.left);
}
}
Added 1 to the calling function.