CODEWITHSUNDEEP
javarecursioniterator
user2272227
user2272227

Reputation: 125

Binary search tree method needed: find minimum value node

Anyone could help me do this: I need a public method for my binary search tree ADT that returns a reference to the information in the node with the smallest value in the tree. The signature of the method is:

public T min()

A. Design an interative version of the method.

B. Design a reccursive version of the method.

C. Which approach is better? Explain please.

This is not a HW or anything, its a practice for myself.

Upvotes: 0

Views: 6283

Answers (3)

Ricardo Cacheira
Ricardo Cacheira

Reputation: 807

As i think that if i gave you the solution you will not learn, i'll give a link to you read more about Binary Search Tree: http://en.wikipedia.org/wiki/Binary_search_tree

After that comment, My way:

public T min() {
    return recMin(root).getInfo();
}

public BSTnode<T> recMin(BSTnode<T> tree) {
    if (tree == null) {
        throw new NoSuchElementException();
    }
    if (tree.left == null) {
        return tree;
    }
    return recMin(tree.left);
}

public T IterationMin(BSTnode<T> tree) {
    if (tree == null) {
        throw new NoSuchElementException();
    }

    while (tree.left != null) {
        tree = tree.left;
    }
    return tree.getInfo();
}

Upvotes: 3

Joel
Joel

Reputation: 5674

A binary search tree has a lower value to the left always, correct? So, you should always go left when you can. If you can't, then you've reached the lowest value.

Upvotes: 2

Porkbutts
Porkbutts

Reputation: 964

On the matter of whether iterative or recursive is better. It really depends. In general recursive solutions tend to be easier to understand, but slower since they consume more and more stack space proportional to the depth of recursion. In this case however, you can come up with a tail-recursive solution which should be easy to understand and just as efficient as the iterative solution.

public BSTNode<T> findMin(BSTNode<T> node) {
    if (node.left == null)     // if there is no left, we are done
        return node;
    return findMin(node.left); // recursively search on the left-child
}

Start by calling this method on the head node.

Upvotes: 2

Related Questions