- Implement the size() method (along with a recursive method) for the BinarySear

Question

- Implement the size() method (along with a recursive method) for the BinarySearchTree class developed in lecture.

- Implement the contains() method (along with a recursive method) for the BinarySearchTree class developed in lecture.

- Implement the toString() method (along with a recursive method) for the BinarySearchTree class developed in lecture that returns a string containing all of the elements in sorted order.

- Implement a recursive method, max() that returns the largest value of the tree.

- Implement a recursive method, min() that returns the smallest value of the tree.

**This is what we implemented in class

public class BinarySearchTree<E extends Comparable<E>> {
private static class Node<E> {
E value;
Node<E> lKid;
Node<E> rKid;
Node(E value) {
this(value, null, null);
}

Node(E value, Node<E> left, Node<E> right) {
this.value = value;
lKid = left;
rKid = right;
}
}

private Node<E> root;

public boolean isEmpty() {
return root==null;
}

public int size() {
return size(root);
}

private int size(Node<E> subroot) {
int size = 0;
if(subroot!=null) {
size = 1 + size(subroot.lKid) + size(subroot.rKid);
}
return size;
}

public boolean add(E value) {
if(value==null) {
throw new NullPointerException("Nulls not welcome here");
}
boolean isChanged;
if(root==null) {
root = new Node<>(value);
isChanged = true;
} else {
isChanged = add(root, value);
}
return isChanged;
}

private boolean add(Node<E> subroot, E value) {
boolean isChanged = false;
int comparison = value.compareTo(subroot.value);
if(comparison>0) {
if(subroot.rKid==null) {
subroot.rKid = new Node<>(value);
isChanged = true;
} else {
isChanged = add(subroot.rKid, value);
}
} else if(comparison<0) {
if(subroot.lKid==null) {
subroot.lKid = new Node<>(value);
isChanged = true;
} else {
isChanged = add(subroot.lKid, value);
}
}
return isChanged;
}
}

Explanation / Answer

The program is working fine. You can sample run the code in the following compilers:

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.