Java Quiz: Iterating over Binary Tree Elements

by

I was thinking this’d make a good Java quiz question. It’s something I have to do all the time in order to make collections accessible in a streaming fashion. Getting an iterator is the easiest way for a client to visit the elements of a collection one at a time. The usual reason is to apply some operation to them. If the collection’s large (sometimes offline, even), it’s less memory intensive to iterate.

Problem: Suppose you have a standard binary tree implementation (see below) and want to implement an instance of java.util.Iterator<Integer> that iterates over the elements. To satisfy the spirit of the exercise, the implementation must take constant time per item iterated and may take at most an amount of memory proportional to the depth of the tree.

Here’s a standard CS 101 binary tree implementation, with the add() and toString() methods for convenience:

    class Tree {
        public final int mVal;
        public Tree mLeft;
        public Tree mRight;
        public Tree(int val) {
            mVal = val;
        }
        public void add(int val) {
            if (val < mVal) {
                if (mLeft == null)
                    mLeft = new Tree(val);
                else
                    mLeft.add(val);
            } else if (val > mVal) {
                if (mRight == null)
                    mRight = new Tree(val);
                else
                    mRight.add(val);
            }
        }
        public String toString() {
            return "(" + mVal + " " 
                  + mLeft + " " 
                  + mRight + ")";
        }

To see how a tree gets built, here’s an example:

    public static void main(String[] args) {
        Integer val = Integer.valueOf(args[0]);
        Tree t = new Tree(val);
        for (int i = 1; i < args.length; ++i)
            t.add(Integer.valueOf(args[i]));
        System.out.println("Tree toString= " + t);
    }

If I compile and run, here’s what I get:

c:carpblogs>java TreeIterator 3 7 8 1 4 5 2 5
Tree toString= (3 (1 null (2 null null)) 
(7 (4 null (5 null null)) (8 null null)))

Hint: It’s easy to walk over the nodes in order using a recursive program. Here’s a simple string builder:

        public String inOrder() {
            return ((mLeft == null) ? "" : mLeft.inOrder())
                + mVal + " "
                + ((mRight == null) ? "" : mRight.inOrder());
        }

If I add the following to my main():

        System.out.println("Values in order = "
                                + t.inOrder());

I get the following line of output:

  Values in order = 1 2 3 4 5 7 8

6 Responses to “Java Quiz: Iterating over Binary Tree Elements”

  1. Jochen L. Leidner Says:

    Hint: (call-with-current-continuation)

  2. Luke Nezda Says:

    preOrder() should really be named inOrder()

  3. lingpipe Says:

    My bad — the traditional name’s indeed “in order” for visiting a node’s left daughter, the node, then it’s right daughter. Post-order visits the node after both daughters and pre-order visits the node before its daughters.

    I took the liberty of correcting the body of the post to cover up my mistake.

  4. Babak Says:

    Interesting quiz question. Here’s a related implementation over the file system:
    http://skwish.sourceforge.net/doc/com/faunos/util/io/file/Traverser.html

    Not quite what your looking for, I admit. One’s a push- and the other a pull-interface, but it does meet your requirement that the memory overhead be linear in the depth of the tree structure.

  5. lingpipe Says:

    Babak’s classes provide a nice example of the other way of solving this problem — with a visitor (in this case, util.io.file.TraverseListener). The visitor implementation gets callbacks for each of the nodes visited for both pre-order and post-order.

    I’d think about simplifying the listener to just be a file listener and then have two ways of calling the listener, pre-order or post-order. Then you can generify the listener to something like LingPipe’s corpus.ObjectHandler<E>. So you’d get a static parser method visitPreOrder(ObjectHandler<File> visitor, File path, FileFilter filter). I like the FileFilter argument — it’s what we used to have in LingPipe as a file visitor. I’d never thought about sibling ordering, but a comparator’s a nice general way to do that.

    But, if you need to have one object visit in both pre-order and post-order, then you need to have the more refined listener interface.
    .

  6. Babak Says:

    Good point, lingpipe. I think I’ll include your single-method visitor interface idea in the next release. Under the current design, if a user wants to visit pre-order, they only implement
    TraverseListener.preorder(File f)
    , leaving the body of the other method empty.

    Like you mention, there are situations where you can use both pre-and post-order events. For example, if a user wants to visit files in pre-order but also wants to count how many files exist under each subdirectory, then they can use the post-order events to implement that count. It’s kinda analogous to capturing a SAX parser’s begin- and end-element events.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s