Computer scienceProgramming languagesJavaCode organizationDesign patternsBehavioral patterns

Iterator

Theory

Tree iterator

Report a typo

Some data structures may require quite complicated logic for iterating over their elements. In this task, you are given a binary search tree to implement the TreeIterator<E> interface which has two methods: boolean hasNext() and E next() which. Create an implementation of TreeIterator that iterates over the elements of BinarySearchTree in ascending order. Also, implement the corresponding TreeIterator<T> iterator() methdod.

The in-order traversal of a binary search tree ensures that its nodes are visited in ascending order.

Write a program in Java 17
import java.util.*;

interface TreeIterator<E> {

boolean hasNext();

E next();
}

class BinarySearchTree<T extends Comparable<T>> {
private Node<T> root;

public void insert(T value) {
root = insert(root, null, value);
}

private Node<T> insert(Node<T> node, Node<T> parent, T value) {
if (node == null) {
Node<T> newNode = new Node<>(value);
newNode.parent = parent;
return newNode;
}

if (node.value.compareTo(value) == 0) {
return node;
}

if (node.value.compareTo(value) > 0) {
node.leftChild = insert(node.leftChild, node, value);
} else {
node.rightChild = insert(node.rightChild, node, value);
}

return node;
}

___

Create a free account to access the full topic