CODEWITHSUNDEEP
recursionbinary-search-tree
Mr.Rabbit
Mr.Rabbit

Reputation: 101

Writing iterative method from recursive method

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;
}

Upvotes: 1

Views: 77

Answers (1)

Anonymoose
Anonymoose

Reputation: 26

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!

Upvotes: 1

Related Questions