LingPipe Blog

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

This entry was posted on January 25, 2009 at 1:34 pm and is filed under Carp's Blog, Java, LingPipe in Use. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.