BST Sequences

A binary search tree was created by traversing through an array from left to right
and inserting each element. Given a binary search tree with distinct elements, print all possible
arrays that could have led to this tree.

ArrayList<LinkedList<Integer> > allSequences(TreeNocte node) {
        Arraylist<Linkedlist<Integer> > result = new Arraylist<Linkedlist<Integer> >();

        if (node == null) {
                result.add(new Linkedlist<Integer>());
                return result;
        }

        Linkedlist<Integer> prefix = new Linkedlist<Integer>();
        prefix.add(node.data);

        /* Recurse on left and right subtrees. */
        Arraylist<Linkedlist<Integer> > leftSeq = al1Sequences(node.left);
        ArrayList<LinkedList<Integer> > rightSeq = al1Sequences(node.right);

        /* Weave together each list from the left and right sides. */
        for (Linkedlist<Integer> left : leftSeq) {
                for (LinkedList<Integer> right : rightSeq) {
                        ArrayList<LinkedList<Integer> > weaved=
                                new Arraylist<Linkedlist<Integer> >();
                        weavelists(left, right, weaved, prefix);
                        result.addAll(weaved);
                }
        }
        return result;
}

/* Weave lists together in all possible ways. This algorithm works by removing the
 * head from one list, recursing, and then doing the same thing with the other
 * list. */
void weaveLists(LinkedList<Integer> first, LinkedList<Integer> second,
                ArrayList<LinkedList<Integer> > results, LinkedList<Integer> prefix) {
        /* One list is empty. Add remainder to [a cloned] prefix and store result. */
        if (first.size() == 0 11 second.size() == 0) {
                Linkedlist<Integer> result = (Linkedlist<Integer>)prefix.clone();
                result.addAll(first);
                result.addAll(second);
                results.add(result);
                return;
        }

        /* Recurse with head of first added to the prefix. Removing the head will damage
         * first, so we'll need to put it back where we found it afterwards. */
        int headfirst= first.removeFirst();
        prefix.addLast(headFirst);
        weavelists(first, second, results, prefix);
        prefix.removelast();
        first.addFirst(headFirst);

        /* Do the same thing with second, damaging and then restoring the list.*/
        int headSecond = second.removeFirst();
        prefix.addLast(headSecond);
        weavelists(first, second, results, prefix);
        prefix.removelast();
        second.addFirst(headSecond);
}