Question

We need a public method for our 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 iterative version of the method. b. Design a recursive version of the method. c. Which approach is better? Explain.

This is for java programming.

Answer 1

public T min() {

    return recMin(root).getInfo();

}

public BSTnode<T> recMin(BSTnode<T> tree) {// Recursive method

    if (tree == null) {

        throw new NoSuchElementException();

    }

    if (tree.left == null) {

        return tree;

    }

    return recMin(tree.left);

}

public T IterationMin(BSTnode<T> tree) {// iterative method

    if (tree == null) {

        throw new NoSuchElementException();

    }

    while (tree.left != null) {

        tree = tree.left;

    }

    return tree.getInfo();

}

It really depends upon the problem which one is better between recursive and iteration, 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. So it is generally better to use iteration.