# BST: All Possible Arrays

Given a binary search tree, print all possible arrays that produce the tree. An array produces a tree by inserting the array’s elements one by one into the tree. The elements are taken from the array from left to right.

**Example.**
Consider the following binary search tree.

Its corresponding arrays are the following.

**Input.**
The input file consists of positive integer `N`

on the first line followed by `N`

test cases. The first line of any given test case consists of a pair of positive integers `M`

and `R`

separated by a single space. Integer `M`

indicates the number of edges in the binary search tree and `R`

is the root of the tree. The `M`

lines that remain in the test case consist of pairs of positive integers `P`

and `C`

corresponding to an edge that goes from parent node `P`

to child node `C`

. The following input file corresponds to the example.

**Output.**
The output consists of all possible arrays for each test case. The arrays that correspond to a given test case must appear in lexicographical order. Each array must appear on a single line. To print an array, print the elements separated by space. For example, the corresponding is the output for the previous input.

# Solution

We build each array from left to right by choosing for every position one node out of a set of possible choices for that position. The set of possible choices for a position is given by the corresponding array prefix. We illustrate the method with the following tree.

We visit the tree starting from the root node. We create array $@acc_0@$. We collect the children of the root in set $@cho_0@$ as possible choices to visit next. The state is the following.

We choose to visit node 3 next. We append 3 to the end of $@acc_0@$ and label the new array $@acc_1@$. We remove 3 from set of choices $@cho_0@$, add the children of 3, and label the new set as $@cho_1@$. The state is the following.

We choose to visit node 8 next. We append 8 to the current array and label the result $@acc_2@$. We remove 8 from the set of choices and label the result $@cho_2@$. The state is the following.

We choose to visit node 1 next. The state is the following.

We choose to visit node 4 next. There are no further choices. We have our first possible array. The state is the following.

To generate the rest of the possible arrays, we backtrack until we can make a different choice and apply the method again.

# Implementation

Here is a Ruby implementation.