CODEWITHSUNDEEP
java
Offspring47
Offspring47

Reputation: 79

Binary Search Tree Iterative Ceiling Method in Java

I'm working on a problem for class I'm stuck on. It involves adding a methods to the Binary Search Tree found here: http://algs4.cs.princeton.edu/32bst/BST.java.html

I need to develop an iterative ceiling method that finds the ceiling for a given key. It cannot be recursive.

Here is my code so far. I understand the basics of the algorithm I am supposed to implement, but I'm finding actually doing so hard to wrap my head around.

Thanks in advance for any help you might be able to offer.

public Key ceiling_i(Key key)
{
    Node t = root;
    for(int i = 0; i < size(); i++){
        int cmp = key.compareTo(t.key);
        if(cmp == 0) return t.key;
        else if(cmp < 0) t = t.left;
        else if(cmp > 0) t = t.right;

    }
    return null;
}

Edit: The main problem I am having is how to deal with the iterations after the first one. According to my book, "If a given key is greater than the key at the root of a BST, then the ceiling of key (the largest key in the BST greater than or equal to key) must be in the right subtree. If key is less than the key at the root, then the ceiling of key could be in the left subtree; if not (or if key is equal to the key at the root), then the key at the root is the ceiling of key." I am not sure how to deal with that in the loop.

Upvotes: 3

Views: 2537

Answers (2)

mszlazak
mszlazak

Reputation: 59

The code from that book is NOT tail-recursive because the first ceiling() call has operations done on it before the returns. 

private Node ceiling(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    if (cmp < 0) { 
        Node t = ceiling(x.left, key); 
        if (t != null) return t;
        else return x; 
    } 
    return ceiling(x.right, key); 
}

Change ceilng() so the recursive calls are an "accumulator" type of tail-call. Do this by passing additional parameters which hold the work done so far.

Null or a node is passed as x.left when cmp < 0. What has "accumulated" so far is a larger-than-item node x found at this conditional test.

In the original version after the the first recursive call, t is either null or some tree node. Node x is then used after if t is null. In a modified version an additional parameter will be passed the x node.

In the other conditional test of cmp > 0 with the tail call, there is no new "accumulated" work since x is smaller than the item and is not used in deciding a return value if x.right is null.

Notice what happens if we pass an "accumulated x" to "larger" in a modified ceiling(x, key, larger) function. In this modified function, the condition "if (x == null) return null" is replaced by "if (x == null) return larger" and all the t-value evaluations are removed after the first recursive call. With the second tail-call just pass null to larger.

So the conversion should look something like this:

private Node ceiling (Node x, Key key, Node larger) {
    if (x == null) return larger;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    if (cmp < 0) { 
        return ceiling(x.left, key, x); 
    } 
    return ceiling(x.right, key, null); 
}

Now the function is tail-recursive and can be further converted into an iterative loop form.

private Node ceiling (Node x, Key key) {
    Node larger = null;
    while (x != null) {
        int cmp = key.compareTo(x.key);
        if (cmp == 0) return x;
        if (cmp < 0) {
            larger = x;
            x = x.left;
        } else {
            x = x.right;
        }
    }
    return larger;
}

Upvotes: 1

usr
usr

Reputation: 171206

Your code is a good start. But your for loop does not make sense to me.

public Key ceiling_i(Key key)
{
    Node t = root;
    Node t largestVisited = null;
    while(t != null) {
        int cmp = key.compareTo(t.key);
        if(cmp == 0) return t.key;
        else if(cmp < 0) { largestVisited = Min(t, largestVisited); t = t.left; }
        else if(cmp > 0) { t = t.right; largestVisited = Min(t, largestVisited); }

    }
    return largestVisited;
}

Node Min(Node a, Node b) { return the node with the smaller key; }

Tip: You could have derived this code by first writing the recursive solution and noticing that it is tail recursive. Tail recursive functions can trivially made non-recursive by just reusing the already existing local variables. No need to open another stack-frame if you won't ever use the old one again.

Upvotes: 2

Related Questions