I'm working on binary search tree homework and am asked to convert a recursive method to an iterative method. Here is the recursive method and below that is my iterative method. This method should return node containing the kth key. My method keeps giving me a NullPointerException and I'm not sure why. Thank you.
Provided code:
public Key select(int k) {
Node node = select(root, k);
if (node==null) {
return null;
} else {
return node.key;
}
}
// Return Node containing kth key (zero based)
private Node select(Node node, int k) {
if (node == null) return null;
int t = size(node.left);
if (t > k)
return select(node.left, k);
else if (t < k)
return select(node.right, k - t - 1);
else
return node;
}
My Code:
public Key selectI(int k) {
return selectI(root, k);
}
private Key selectI(Node node, int k) {
Node curr = node;
while (curr != null) {
int t = size(node.left);
if (t > k) {
curr = node.left;
} else if (t < k) {
curr = node.right;
k = (k - (t - 1));
} else
return curr.key;
}
return null;
}
k - t - 1while selecting right node....???