Binary Trees: In-order Iterator: Java

Question

How would I go about writing an iterator to iterate over each value of a binary tree in "in-order" fashion? I should be using a stack. BinaryNode is a simple node class with pointers to "left" and "right" nodes. Here is what I have so far:

class InOrderIterator implements Iterator<T> {

    private Stack<BinaryNode> stack;

    public InOrderIterator(BinarySearchTree<T>.BinaryNode root) {
        stack = new Stack<BinaryNode>();
        stack.push(root);
    }

    @Override
    public boolean hasNext() {
        while (!this.stack.isEmpty() && stack.peek() == NULL_NODE)
            this.stack.pop();
        return !this.stack.isEmpty();
    }

    @Override
    public T next() {
        //TODO

        if (!this.hasNext())
            throw new NoSuchElementException("No more nodes in tree!");

        BinaryNode current = this.stack.pop();
        BinaryNode output = null;

        while(current != NULL_NODE){
            this.stack.push(current);
            current = current.left;
        }

        if(current == NULL_NODE){
            if(!this.stack.isEmpty()){
                output = this.stack.pop();
                return output.data;
            }
        }
        return null;
    }
}

I have the basic algorithm down, but I can't seem to convert it to java code.

Answer 1

public class BinaryTreeNode {
    private int element; //element stored at this node

    private BinaryTreeNode left, right; 

    public BinaryTreeNode() {  }

    public BinaryTreeNode(int element) {
        setElement(element);
        setLeft(null);
        setRight(null);
    }

    //returns the elements stored at this position
    public int element() {
        return element;
    }

    //sets the elements  stored at this position
    public void setElement(int e) {
        element = e;
    }

    //return the left child of this position
    public BinaryTreeNode getLeft() {
        return    left;
    }

    //set the left chid of this position
    public void  setLeft(BinaryTreeNode l) {
        left = l;
    }

    //return the right child of this position
    public BinaryTreeNode getRight() {
        return    right;
    }

    //sets the right child of this position
    public void  setRight(BinaryTreeNode r) {
        right = r;
    }      

}

---

public class TestBTN {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        BinaryTreeNode root = null, right, left, node = null;

        int arrayInt[] = {25, 20, 7, 13, 33, 50, 45, 17, 30, 55};

        for (int i = 0; i < arrayInt.length; i++) {
            if (root == null) {
                root = node = new BinaryTreeNode(arrayInt[0]);
            }//endIf
            else {
                node = new BinaryTreeNode(arrayInt[i]);
                BinaryTreeNode s, p;
                p = s = root;
                while (s != null) {
                    p = s;
                    if (node.element() > s.element()) {
                        s = s.getRight();
                    } else {
                        s = s.getLeft();
                    }
                }//endWhile
                if (node.element() > p.element()) {
                    p.setRight(node);
                } else {
                    p.setLeft(node);
                }
            }//emdElse
        }//endFor

        //printing
        //Print(root);
        //PostOrder(root);
        //PreOrder(root);
        InOrder(root);
        //System.out.println("\nBinaryTreeNode");

    }//endMain

    private static void Print(BinaryTreeNode node) {
        if (node != null) {
            System.out.print(node.element() + " ");
            Print(node.getLeft());
            Print(node.getRight());
        }//endIf
    }//endPrint

    static void PostOrder(BinaryTreeNode ptr) {
        if(ptr != null) {
            PostOrder(ptr.getLeft());
            PostOrder(ptr.getRight());
            System.out.print(ptr.element()+" ");
        }//endIf
    }//endPost

    static void PreOrder(BinaryTreeNode ptr) {
        if(ptr != null) {
            System.out.print(ptr.element()+" ");
            PreOrder(ptr.getLeft());
            PreOrder(ptr.getRight());

        }
    }        

    static void InOrder(BinaryTreeNode ptr) {
        if(ptr != null) {
            InOrder(ptr.getLeft());
            System.out.print(ptr.element()+" ");
            InOrder(ptr.getRight());
        }
    }
}

Answer 2

Think about invariants. You have a stack of nodes. What does it mean for a node to be on the stack?

Might I suggest: A node on the stack represents a "half-tree", a node and its entire right subtree, and the stack holds all the half-trees that together make up all the nodes that have not been returned from next() yet.

In what order should those half-trees be pushed on the stack? Answering that question gives you your invariant condition, the property that will be preserved as your code runs.

Satisfy yourself that your invariant implies that the top of the stack must be whatever next() is going to return next. When you pop it off to return it, you're going to have to somehow deal with its right subtree before returning. From your invariant, it should be obvious how to do that.

If you don't consciously and explicitly think about what your variables mean and what your invariants are, your coding efforts are going to be undirected. You're going to flail around, writing spaghetti code. Once you've done that, though, the code will write itself.