Iterator for a Binary Search Tree do not go down the tree

Question

I've been struggling with implementing a Binary Search Tree with the Iterator method. I've been checking out this algorithm out on WikiPedia:

def search_recursively(key, node):
    if node is None or node.key == key:
        return node
    if key < node.key:
        return search_recursively(key, node.left)
    # key > node.key
    return search_recursively(key, node.right)

I translated it to Java:

public Iterator<T> iterator()
    {
        return new Iterator<T>()
        {
            private int count = 0;

            @Override
            public boolean hasNext()
            {
                return count++ < size;
            }

            @Override
            public T next()
            {
                return search(root, root.word);
            }

            public T search(BST root, T word)
            {
                if (root == null || root.word.compareTo(word) == 0)
                {
                    return root.word;
                }

                if (root.word.compareTo(word) < 0)
                {
                    return search(root.left, word);
                }

                return search(root.right, word);
            }
        };

When trying to run the program I only get the root element of the BST:

MyWordSet bst = new MyWordSet();

T bst = new T("one");
T bst = new T("two");
T bst = new T("three");
T bst = new T("four");
T bst = new T("five");
T bst = new T("six");

bst.add(w1);
bst.add(w2);
bst.add(w3);
bst.add(w4);
bst.add(w5);
bst.add(w6);

Iterator<T> it = bst.iterator();

while (it.hasNext())
{
    System.out.println(it.next());
}

So the output is:

one
one
one
one
one
one

So why does this method inside my Iterator not work for me to get to the whole tree? I really can't figure out what is wrong here and why it only prints out one when it should go down the tree.

Answer 1

You simply do not update the current_node.

The equivalent of current_node = node is missing.

---

Well, after having changed the code, here revised answer:

import java.util.Iterator;
import java.util.Stack;

/**
 *
 * @author jk
 */
public class BSTIterator<T> implements Iterator<T> {

    public static final class BST<T> {

        private BST<T> left;
        private BST<T> right;
        private T word;

        private BST(T word) {
            this.word = word;

        }

    }
    private final Stack<BST<T>> stackBST = new Stack<>();

    public BSTIterator(final BST<T> root) {
        // push all most left entries of the tree to the stack
        BST<T> currBST = root;
        while (currBST != null) {
            stackBST.push(currBST);
            currBST = currBST.left;
        }
    }

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

    @Override
    public T next() {
        BST<T> currBST = stackBST.pop();

        // check if we are on the most right entry
        final boolean notMostRightEntry = currBST.right != null;
        if (notMostRightEntry) {
            // take next right entry 
            BST<T> nextBST = currBST.right;
            while (nextBST != null) {
                // push this next right entry on the stack
                stackBST.push(nextBST);
                nextBST = nextBST.left;
            }
        }
        return currBST.word;
    }

    public static void main(String[] args) {
        BST<Integer> root = new BST<>(20);
        root.left = new BST<>(5);
        root.right = new BST<>(30);
        root.left.right = new BST<>(10);
        root.right.left = new BST<>(25);
        root.right.right = new BST<>(40);
        root.right.left = new BST<>(35);
        root.right.left.left = new BST<>(32);
        for (Iterator<Integer> bstIt = new BSTIterator<>(root); bstIt.hasNext();) {
            System.out.println("val: " + bstIt.next());

        }
    }

}