# 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.

EXAMPLE

``````Input: 2
/ \
1   3

Output: {2, 1, 3}, {2, 3, 1}
``````

## Code

``````ArrayList<LinkedLIst<Integer>> allSequences(TreeNode node) {

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

ArrayList<LinkedLIst<Integer>> leftSeq = allSequences(node.left);
ArrayList<LinkedList<Integer>> rightSeq = allSequences(node.right);

// weave
for (LinkedList<Integer> left : leftSeq) {
for (LinkedList<Integer> right : rightSeq) {
weaveLists(left, right, weaved, prefix);
}
}
return result;
}

// one list is empty. Add remainder to [a cloned] prefix and store result.
if (first.size() == 0 || second.size() == 0){
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();