I am having trouble implementing a solution using a binary search tree that returns the key of the node based on it's rank in O(N) worst case running time.
Every idea i have (listed below) results in O(N^2) or sends me to a dead end. This almost seems impossible.
i would greatly appreciate any insight on how this might be done or if one of my ideas may have a work around.
- Use a while loop to cycle down to the leftmost node and start from there counting upwards but there is no way to access a parent node while meeting maintaining O(N).
- Use a placeholder node to traverse each node using a counter to countdown to the desired rank but i cant move to the parent node after checking if child's child's node is null.
- Use the key values to cycle through instead of the ranks but this result just send gave me an O(N^2) running time as well.
- I also thought of using an array/stack/queue but filling it is O(N) and then running through that again is another O(N) creating an O(N^2) scenario again.
This is my exisiting code that is currently O(N^2):
public int size() { // number of nodes inside this BST,
if(root==null) { //first check if tree is empty
return 0;
}
else {
return rSize(root); //returns recursive size method below
}
}
private int rSize(Node node){ //traverses through each left then right node and returns the size/rank count
if(node==null){
return 0;
}
else {
return (rSize(node.left) + rSize(node.right) + 1);
}
}
public Key rank(int k) { //k is the desired rank of node
Node node = select(root, k);
if (node==null) {
return null;
} else {
return node.key;
}
}
private Node rank(Node node, int k) {
if (node == null) return null;
int t = rSize(node.left);
if (t > k)
return select(node.left, k);
else if (t < k)
return select(node.right, k - t - 1);
else
return node;
}
