Traversing binary trees through and through

Question

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<T> {
 public final T value;
 public TreeNode<T> left;
 public TreeNode<T> 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 <T> Iterator<T> preOrderIterator(TreeNode<T> root) {
 return new PreOrderIterator<>(root);
 }
 public static <T> Iterator<T> inOrderIterator(TreeNode<T> root) {
 return new InOrderIterator<>(root);
 }
 public static <T> Iterator<T> postOrderIterator(TreeNode<T> root) {
 return new PostOrderIterator<>(root);
 }
 public static <T> Iterator<T> levelOrderIterator(TreeNode<T> root) {
 return new LevelOrderIterator<>(root);
 }
 private static class PreOrderIterator<T> implements Iterator<T> {
 private final Stack<TreeNode<T>> stack = new Stack<>();
 private PreOrderIterator(TreeNode<T> root) {
 if (root != null) {
 stack.push(root);
 }
 }
 @Override
 public boolean hasNext() {
 return !stack.isEmpty();
 }
 @Override
 public T next() {
 TreeNode<T> node = stack.pop();
 if (node.right != null) {
 stack.push(node.right);
 }
 if (node.left != null) {
 stack.push(node.left);
 }
 return node.value;
 }
 }
 private static class InOrderIterator<T> implements Iterator<T> {
 private Stack<TreeNode<T>> stack = new Stack<>();
 private InOrderIterator(TreeNode<T> root) {
 moveToLeftMost(root);
 }
 private void moveToLeftMost(TreeNode<T> node) {
 while (node != null) {
 stack.push(node);
 node = node.left;
 }
 }
 @Override
 public boolean hasNext() {
 return !stack.isEmpty();
 }
 @Override
 public T next() {
 TreeNode<T> current = stack.pop();
 moveToLeftMost(current.right);
 return current.value;
 }
 }
 private static class PostOrderIterator<T> implements Iterator<T> {
 private Stack<TreeNode<T>> stack = new Stack<>();
 private PostOrderIterator(TreeNode<T> root) {
 moveToNextLeaf(root);
 }
 private void moveToNextLeaf(TreeNode<T> node) {
 while (node != null) {
 stack.push(node);
 node = node.left != null ? node.left : node.right;
 }
 }
 @Override
 public boolean hasNext() {
 return !stack.isEmpty();
 }
 @Override
 public T next() {
 TreeNode<T> current = stack.pop();
 if (!stack.isEmpty()) {
 TreeNode<T> parent = stack.peek();
 if (parent.right != current) {
 moveToNextLeaf(parent.right);
 }
 }
 return current.value;
 }
 }
 private static class LevelOrderIterator<T> implements Iterator<T> {
 private final Queue<TreeNode<T>> queue = new LinkedList<>();
 private LevelOrderIterator(TreeNode<T> root) {
 queue.add(root);
 }
 @Override
 public boolean hasNext() {
 return !queue.isEmpty();
 }
 @Override
 public T next() {
 TreeNode<T> current = queue.poll();
 if (current.left != null) {
 queue.add(current.left);
 }
 if (current.right != null) {
 queue.add(current.right);
 }
 return current.value;
 }
 }
}

Unit tests:

package com.janosgyerik.examples.tree.binarytree;
import org.junit.Test;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import static org.junit.Assert.*;
public class IteratorsTest {
 // example tree from http://en.wikipedia.org/wiki/Tree_traversal
 /*
 F
 B G
 A D I
 C E H
 */
 private final TreeNode<Character> root;
 public IteratorsTest() {
 root = new TreeNode<>('F');
 root.left = new TreeNode<>('B');
 root.left.left = new TreeNode<>('A');
 root.left.right = new TreeNode<>('D');
 root.left.right.left = new TreeNode<>('C');
 root.left.right.right = new TreeNode<>('E');
 root.right = new TreeNode<>('G');
 root.right.right = new TreeNode<>('I');
 root.right.right.left = new TreeNode<>('H');
 }
 static <T> List<T> iterateToList(Iterator<T> iterator) {
 List<T> list = new LinkedList<>();
 while (iterator.hasNext()) {
 list.add(iterator.next());
 }
 return list;
 }
 @Test
 public void testPreOrderIterator() {
 Iterator<Character> iterator = Iterators.preOrderIterator(root);
 assertEquals(Arrays.asList('F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H'), iterateToList(iterator));
 }
 @Test
 public void testInOrderIterator() {
 Iterator<Character> iterator = Iterators.inOrderIterator(root);
 assertEquals(Arrays.asList('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'), iterateToList(iterator));
 }
 @Test
 public void testPostOrderIterator() {
 Iterator<Character> iterator = Iterators.postOrderIterator(root);
 assertEquals(Arrays.asList('A', 'C', 'E', 'D', 'B', 'H', 'I', 'G', 'F'), iterateToList(iterator));
 }
 @Test
 public void testLevelOrderIterator() {
 Iterator<Character> iterator = Iterators.levelOrderIterator(root);
 assertEquals(Arrays.asList('F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'H'), iterateToList(iterator));
 }
}

I'm looking for a review of all aspects of all the above code.

Answer 1

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 (and efficient). 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...

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

Answer 2

I'm not 'feeling' the concept here. There's a disconnect between what you have, and what you're doing. You are asking for an iterator, but passing in a node.... that makes no sense. You should be passing in a Tree.

The TreeNode should not be public... it should be attached to a new Tree class in a more restricted way. Perhaps a Tree interface and then a number of implementations like BalancedTree, etc.

So, it's a design issue...

Then, about the Iterators, you're taking advantage of Java8 Default methods on the Iterator (the default remove() implementation), but then really, you should be streaming things, not iterating them. A Spliterator is what you should be implementing.

In a sense, I see your code as being a good solution to a 'local' problem, but the way you describe the code is that it should be some form of API, and, as a library, it's problematic.

• maaartinus: I was thinking about the first paragraph... and there is File which is a tree node, but there's no corresponding tree. Each file has a subtree below it and it's fine. +++ So maybe a Tree makes only sense when you really need to abstract away the nodes like in a TreeMap.