Create Iterable for BST-backed Symbol Table

Question

For an assignment, I need to create an iterable that contains all keys for a symbol table backed by a binary search tree. I'm familiar with how to do this for a linked list, but can't seem to find any examples online about how to do this for a BST. For a linked list, for example, I'd use something like this:

public Iterable<Key> keys() { 
    Queue<Key> queue = new Queue<Key>();
    for (Node x = first; x != null; x = x.next)
    queue.enqueue(x.key);
    return queue;
}

But I'm not quite sure how to convert that so it holds all keys for my BST. Can someone provide guidance or a link to a source that covers this topic?

Answer 1

If you want to traverse left first, you can implement it using a stack.

static class Node<T> {
    T value;
    Node<T> left, right;
    
    Node(T value, Node<T> left, Node<T> right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

and

static class BST<T> implements Iterable<T> {
    Node<T> root;
    
    public BST(Node<T> root) {
        this.root = root;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<>() {
            Deque<Node<T>> stack = new LinkedList<>();
            { pushAllLeft(root); }

            private void pushAllLeft(Node<T> node) {
                for ( ; node != null; node = node.left)
                    stack.push(node);
            }

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

            @Override
            public T next() {
                Node<T> current = stack.pop();
                pushAllLeft(current.right);
                return current.value;
            }
        };
    }
}

and

public static void main(String[] args) {
    BST<Integer> bst = new BST<>(
        new BST.Node<>(3,
            new BST.Node<>(1,
                new BST.Node<>(0, null, null),
                new BST.Node<>(2, null, null)),
            new BST.Node<>(5,
                new BST.Node<>(4, null, null),
                new BST.Node<>(6, null, null))));

    for (int n : bst)
        System.out.println(n);
}

output:

0
1
2
3
4
5
6