In-order iterator for binary tree

Question

How can I write a Java iterator (i.e. needs the next and hasNext methods) that takes the root of a binary tree and iterates through the nodes of the binary tree in in-order fashion?

Answer 1

The first element of a subtree is always the leftmost one. The next element after an element is the first element of its right subtree. If the element does not have a right child, the next element is the element's first right ancestor. If the element has neither a right child nor a right ancestor, it is the rightmost element and it's last in iteration.

I hope my code is human readable and covers all cases.

public class TreeIterator {
    private Node next;

    public TreeIterator(Node root) {
        next = root;
        if(next == null)
            return;

        while (next.left != null)
           next = next.left;
    }

    public boolean hasNext(){
        return next != null;
    }

    public Node next(){
        if(!hasNext()) throw new NoSuchElementException();
        Node r = next;

        // If you can walk right, walk right, then fully left.
        // otherwise, walk up until you come from left.
        if(next.right != null) {
            next = next.right;
            while (next.left != null)
                next = next.left;
            return r;
        }

        while(true) {
            if(next.parent == null) {
                next = null;
                return r;
            }
            if(next.parent.left == next) {
                next = next.parent;
               return r;
            }
            next = next.parent;
        }
     }
 }

Consider the following tree:

     d
   /   \
  b     f
 / \   / \
a   c e   g

• The first element is "fully left from the root"
• a does not have a right child, so the next element is "up until you come from left"
• b does have a right child, so iterate b's right subtree
• c does not have a right child. It's parent is b, which has been traversed. The next parent is d, which has not been traversed, so stop here.
• d has a right subtree. Its leftmost element is e.
• ...
• g has no right subtree, so walk up. f has been visited, since we've come from right. d has been visited. d has no parent, so we cannot move further up. We have come from the rightmost node and we're done iterating.

Answer 2

To get the next entry, 'nextEntry()', for the iterator, I looked at snippets from java.util.TreeMap pasted below. In plain English, I'd say you make sure the root node is not null first else return null. If it is not, vist the right node if it is not null. Then visit the left (if not null) and visit that one's left repeatedly in a while loop until hitting null. If the originial right node is null then instead of all that, visit the parent node if that is not null. Now enter a while loop where you vist the parent until it's either null or the node you're currently visiting has its right (child) node equal to your last position. Now return whatever entry you're sittng on. Failing all those options, return the (original) root node. 'HasNext()' merely checks if this "next entry" you are returning is null or not.

public final boolean hasNext() {
     return next != null;
}

final TreeMap.Entry<K,V> nextEntry() {
    TreeMap.Entry<K,V> e = next;
    if (e == null || e.key == fenceKey)
        throw new NoSuchElementException();
    if (m.modCount != expectedModCount)
        throw new ConcurrentModificationException();
    next = successor(e);
    lastReturned = e;
    return e;
}

static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

Answer 3

It's pretty straight forward, for in-order traversal you visit the left child if there is one, then the root node, then the right child:

visit_node(node)
   if node.left: visit_node(node.left)
   // visit the root node
   if node.right: visit_node(node.right)

Diagram:

     a 
   /   \        (in-order traversal would give bac)
  b     c