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.
Consider a simple binary search tree with three elements. The root of the tree must have been inserted first - if a different node was inserted first, that node would be the root. After the root has been inserted, the left and right children could have been inserted in any order. The tree below has two possible sequences:
If we have two sequences which define the order of insert for the left and right subtrees, the set of generalized sequences is defined by all the sequences for which the order of the subsequences is preserved. This can be made more concrete with an example. Let’s say the left subtree was created by the following sequence:
and the right subtree was created by the following sequence:
In order to create the superset of sequences which could have created the entire tree, we need to weave elements from the left sequence with elements from the right sequence. The following are possible sequences which created the two subtrees.
A,B,C,D,E,F A,B,D,C,E,F A,D,B,E,C,F D,A,E,B,F,C D,E,A,F,B,C D,E,F,A,B,C
We can write a function which recursively generates the set of possible sequences, given two input sequences. Notice that when building
prefix, we cover both cases by removing an element from both
sequence_2. After the
weave_lists call returns, we restore both
prefix and the
sequence to their original state so that we don’t disturb the other calls on the stack.
def weave_lists(sequence_1, sequence_2, results, prefix): if(len(sequence_1) == 0) or (len(sequence_2) == 0): result = prefix[:] result += sequence_1 result += sequence_2 results.append(result) return new_1 = sequence_1.pop(0) prefix += new_1 weave_lists(sequence_1, sequence_2, results, prefix) prefix.pop() sequence_1.insert(0, new_1) new_2 = sequence_2.pop(0) prefix += new_2 weave_lists(sequence_1, sequence_2, results, prefix) prefix.pop() sequence_2.insert(0, new_2)
Now, we need to build another recursive function which builds the sequences.
def generate_sequences(node): results =  if(node == None): return [] prefix = [node.key] left_sequences = generate_sequences(node.left) right_sequences = generate_sequences(node.right) for i in range(len(left_sequences)): for j in range(len(right_sequences)): weaved =  weave_lists(left_sequences[i], right_sequences[j], weaved, prefix) results.append(weaved) return results