How to implement remove() method in binary search tree iterator

2.1k Views Asked by At

I'm implementing the binary search tree, here is the most important part of my code:

import java.util.*;

public class BinaryTree<K extends Comparable<K>, V> implements Iterable<BinaryTree.Entry> {
    private Entry<K, V> root;

    // inOrder iterator
    @Override
    public Iterator<BinaryTree.Entry> iterator() {
        return new InOrderIterator(root);
    }

    class InOrderIterator implements Iterator<BinaryTree.Entry> {
        Entry root;
        Stack<Entry> stack = new Stack<>();

        private void pushLeftChildren(Entry root) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
        }

        public InOrderIterator(Entry root) {
            this.root = root;
            pushLeftChildren(root);
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public Entry next() {
            if (!hasNext()) {
                throw new NoSuchElementException("All nodes have been visited!");
            }

            Entry poped = stack.pop();
            pushLeftChildren(poped.right);

            return poped;
        }

        @Override
        public void remove() {

        }
    }

    class Entry<K extends Comparable<K>, V> {
        K key;
        V value;
        Entry<K, V> left;
        Entry<K, V> right;


        Entry(K key, V value, Entry<K, V> left, Entry<K, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}

So, I want to implement remove() method in that inOrder traversing iterator, even usually it's marked as throwing unsupported operation exception. Can you give me some advice how to do that if it is possible?

0

There are 0 best solutions below