1

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;
}
5
  • 1
    why you are giving k - t - 1 while selecting right node....??? Commented Nov 26, 2015 at 6:16
  • @AbbasGabru It is provided with the original recursion code. It's a good question and I'm not sure why that is either. There is an example of the recursive code here link which also uses k-t-1 for selecting the right node. I would appreciate it if anyone can help answer this question. Commented Nov 26, 2015 at 6:34
  • 1
    this is what you have written ` This method should return node containing the kth key.` but the code you are providing is the code that return node that contain kth smallest key.... so what i want to ask is if you are returning node that contains key then no need to decrement it (in your code)... Commented Nov 26, 2015 at 7:10
  • @AbbasGabru I have made changes to my code above. I tested my code without decrementing it, but that causes me to be in an infinite loop. I've tried incrementing t in my code that is where I am now and it only returns the first value after the root. In the BST with the following numbers [5, 50, 20, 78] it's returning 50 back when I want it to return 78. Any ideas? Thanks. Commented Nov 27, 2015 at 1:59
  • I've cleaned up the code by taking out some not needed variables. However, I'm getting NullPointerException. This seems to happen whenever I change from "curr = node.right;" to "curr = curr.right;". Any suggestion is appreciated. Commented Nov 28, 2015 at 6:09

1 Answer 1

1

The problem seems to be that you are not updating the value for k. This is normally done recursively, but you have to do it mathematically if you are going to make an iterative function. When you pass to the left (t > k) you continue searching for the node with the size of k. When you pass to the right (t < k) you are searching for a node with size k = (k - (t - 1)). Eventually t and k will either be equal or zero, in which case you've found the node you're looking for!

Also make sure that you are constantly updating the size of the current node you are looking at. You don't want to only look at the size of the tree, this ruins the mathematical relationship between your t and k values, which will cause the program to run until there are no more nodes to look at!

Sign up to request clarification or add additional context in comments.

2 Comments

Thank you for your suggestions. I want to make sure I understand you correctly. So would I need to update both t, the size, and k, the node that we're looking for inside the if and else statements? Would I not need to update k when passed to the left but would need to update k to k = (k-(t-1)) when passed to the right?
Thank you! I was able to solved this problem with your suggestions.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.