Agfdhyk

For a binary tree object I'm implementing with the private fields

X key;

Y value;

Tree<X,Y> left;

Tree<X,Y> right;

I have a method public Tree<X,Y> subset(X startKey, X endKey) that needs to return a Tree including all of the keys in between the node with startKey and the node with endKey, and their corresponding values. This method also needs to be performed using recursion.

The problem I'm having is that I can't figure out a way to get a tree (which would probably look like a LinkedList) that ends with endKey, without including endKey.left and endKey.right. I figured I should start by calling the method recursively on either the left or right tree of the root depending on if the startKey is bigger or smaller than the root key, so:

if (this.key.compareTo(startKey) < 0) this.right.subset(startKey, endKey);

else if (this.key.compareTo(startKey > 0) this.right.subset(startKey, endKey);

That would keep navigating through the tree until it arrives on the node containing the key startKey. When I get to that point, I copy this to a new tree so I can avoid editing the original tree. This new tree has the node with startKey as its root, and then has the same children as the original.

This is where I'm stuck. The problems I know I'll have to deal with is navigating to endKey, making sure I stop there and don't include endKey.left or endKey.right, and return the subset correctly even as the method is "unwinding" from the recursive calls. I'm thinking that if I want to stop at endKey, I'll have to somehow keep a reference to its parent node, so that I can set the parent node's left or right child to the key/value pair in order to cut off the rest of endKey's children. However, since I don't really have node objects, and I can't add any methods or constructors, I don't know how I'd be able to maintain a reference to a parent tree. I also don't know how to attempt to pull this off while maintaining startKey as the root of the new tree.

In other words, I think I've managed to get a subset of a tree that starts on a lower level and continues to the bottom of the original tree. How can I recursively eliminate the children at the bottom I don't want and return my new subset?

If you treat it as a view you don't actually cut it out, you just limit the methods to the range of the subset. When using iterator() e.g. the submap just has its own implementation of Iterator which start at the lower bound of the submap and just returns hasNext() == false when the upper bound is reached. The user won't notice that he is actually iterating over the original tree, because it's completly hidden. I hope this example gives you an idea about it.

public interface Tree<X, Y> extends Iterable<Tree<X, Y>> {

    X getKey();

    X getValue();

    Tree<X, Y> floor(X key);

    Tree<X, Y> ceiling(X key);

    Tree<X, Y> subTree(X lo, X hi);

    // ...

}



public class TreeImpl<X, Y> implements Tree<X, Y> {

    final X key;

    Y value;

    TreeImpl<X, Y> left, right;



    public TreeImpl(X key, Y value) {

        this.key = key;

        this.value = value;

    }



    @Override

    public Iterator<Tree<X, Y>> iterator() {

        return new TreeItr();

    }



    // Iterator starting at the most left to the most right;

    private class TreeItr implements Iterator<Tree<X, Y>> {

        // ...

    }



    @Override

    public Tree<X, Y> subTree(X lo, X hi) {

        return new SubTree<>(this, lo, hi);

    }



    private static class SubTree<X, Y> implements Tree<X, Y> {

        final Tree<X, Y> backing;

        final X lo, hi;



        public SubTree(Tree<X, Y> backing, X lo, X hi) {

            this.backing = backing;

            this.lo = lo;

            this.hi = hi;

        }



        @Override

        public Iterator<Tree<X, Y>> iterator() {

            return new SubTreeItr(backing.ceiling(lo), backing.floor(hi))

        }



        // Iterator starting at 'from' and returning 'hasNext() == false' after 'to'

        // has returned

        private class SubTreeItr implements Iterator<Tree<X, Y>> {

            final Tree<X, Y> from, to;



            public SubTreeItr(Tree<X, Y> from, Tree<X, Y> to) {

                this.from = from;

                this.to = to;

            }



            //...

        }



        @Override

        public Tree<X, Y> subTree(X lo, X hi) {

            // Check if lo > this.lo && hi < this.hi

            return new SubTree<>(backing, lo, hi);

        }

    }

}