Traversing binary trees through and through

Given a binary tree, it's quite common to perform some operation on all nodes while traversing pre-order, in-order, post-order or level-order, depending on the task at hand. For example you might want to extract sorted elements from a binary search tree, for which in-order traversal is handy. Or do a breadth first search to find the shortest path to an element from the root, for which level-order traversal is handy.

Given a TreeNode defined as:

public class TreeNode {
    public final T value;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(T x) {
        value = x;
    }

    @Override
    public String toString() {
        return String.valueOf(value);
    }
}

The utility class to generate the various iterators:

```
package com.janosgyerik.examples.tree.binarytree;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Iterators {

private Iterators() {
// utility class, forbidden constructor
}

public static Iterator preOrderIterator(TreeNode root) {
return new PreOrderIterator<>(root);
}

public static Iterator inOrderIterator(TreeNode root) {
return new InOrderIterator<>(root);
}

public static Iterator postOrderIterator(TreeNode root) {
return new PostOrderIterator<>(root);
}

public static Iterator levelOrderIterator(TreeNode root) {
return new LevelOrderIterator<>(root);
}

private static class PreOrderIterator implements Iterator {
private final Stack> stack = new Stack<>();

private PreOrderIterator(TreeNode root) {
if (root != null) {
stack.push(root);
}
}

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

@Override
public T next() {
TreeNode node = stack.pop();
if (node.right != null) {
stack.push(

TreeNode

I'm not sure, if you find this applicable, but using it the code may get more generally usable.

Given a TreeNode defined as:

This is the first problem. There are quite a few tree nodes out there, which don't extend TreeNode, most notably File, XMLNode, XmlNode (really, both exist), and javax.swing.tree.TreeNode. An interface wouldn't help here unless we expect Oracle to retrofit Java. I'm aware that all my examples are wrong as none of them is a binary tree.

You can try to wrap e.g. File in a subclass of your TreeNode, but then you need a way to get the latter given the former and new MyFileTreeNode(file) doesn't help as you need exactly the same instance as before.

The easy way is to define a class like

public abstract class TreeNodeAdapter {
    public TreeNode left(T value);
    public TreeNode right(T value);
}

and work with the values directly.
Iterators

import java.util.Stack;

Don't use this synchronized crap. Unfortunately, ArrayList lacks pop and peek, which makes using it more verbose, but otherwise it's fine (and efficient). There's also ArrayDeque, which has all needed operations, albeit named differently.

public static  Iterator levelOrderIterator(TreeNode root) {

This could use some short documentation about what it does (the others are obvious).

public static  Iterator preOrderIterator(TreeNode root) {
    return new PreOrderIterator<>(root);
}

It'd nicer to have a PreOrderIterable and call

for (T t : root.preorderIterable()) {....}

but it'd mean to write quite some boilerplate.

private PreOrderIterator(TreeNode root) {
        if (root != null) {
            stack.push(root);
        }
    }

So you're silently converting null into an empty iterator. Is this wise? I strongly prefer being fail-fast, but I guess, that null is actually the empty tree and then everything's fine...

Maybe except for identifying nodes with trees as rolfl wrote. That feels a bit hacky, but looking at my File example above, there's no corresponding tree class and nobody seems to miss it.

public T next() {
        TreeNode node = stack.pop();
        ...
    }

You throw an EmptyStackException, but it should be a NoSuchElementException. This requires an explicit hasNext() check at the beginning.

Or you can extend Guava's AbstractIterator. This would also help you with missing remove() - you code can't compile or am I blind??? I see, default method, so Java 8 only. Just add a big warning sign "not for android and not for maaartinus).
IteratorsTest

From the example tree it's pretty hard to see if your test cases are correct. Without looking at the picture, I have no idea if

'A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'

is the right thing. And even with the picture it takes a while. I'd go for a tree like

T
    L       R
LL    LR       RR
   LRL  LRR  RRL

I guess, you could use more tests, and then it gets important. I'd also join the lists as

"A C E D B H I G F"

is not such a pain to type.

Some of the iterators are rather complicated and I can't see if PostOrderIterator is right. If I really wanted to be sure, I'd add some pseudo-randomly generated trees and compare the iterator-produced list with what a recursive implementation does (which is e.g. for the first three iterators very trivial).

StackExchange Code Review Q#92794, answer score: 5