Return to Answer

• 1

• 13.6k
• 1
• 35
• 74

• 13.6k
• 1
• 35
• 74

##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<T> {
 public TreeNode<T> left(T value);
 public TreeNode<T> 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. There's also ArrayDeque, which has all needed operations, albeit named differently.

public static <T> Iterator<T> levelOrderIterator(TreeNode<T> root) {

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

public static <T> Iterator<T> preOrderIterator(TreeNode<T> 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<T> 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.

 public T next() {
 TreeNode<T> 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???

##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).