Friday, July 1, 2016

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.

if (node == null) {
return result;
}

/* Recurse on left and right subtrees. */

/* Weave together each list from the left and right sides. */
for (Linkedlist<Integer> left : leftSeq) {
for (LinkedList<Integer> right : rightSeq) {
weavelists(left, right, weaved, prefix);
}
}
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. */
/* One list is empty. Add remainder to [a cloned] prefix and store result. */
if (first.size() == 0 11 second.size() == 0) {
return;
}

* first, so we'll need to put it back where we found it afterwards. */
weavelists(first, second, results, prefix);
prefix.removelast();

/* Do the same thing with second, damaging and then restoring the list.*/
weavelists(first, second, results, prefix);
prefix.removelast();