Given a BST and its root, print all sequences of nodes which give rise to the same bst

Question

Given a BST, find all sequences of nodes starting from root that will essentially give the same binary search tree.

Given a bst, say

  3
 /  \
1    5

the answer should be 3,1,5 and 3,5,1.

another example

       5
     /   \
    4     7
   /     / \
  1     6   10

the outputs will be

5,4,1,7,6,10

5,4,7,6,10,1

5,7,6,10,4,1

etc

The invariant here however is that the parent's index must always be lesser than its children. I am having difficulty implementing it.

Answer 1

I assume you want a list of all sequences which will generate the same BST.
In this answer, we will use Divide and Conquer.
We will create a function findAllSequences(Node *ptr) which takes a node pointer as input and returns all the distinct sequences which will generate the subtree hanging from ptr. This function will return a Vector of Vector of int, i.e. vector<vector<int>> containing all the sequences.

The main idea for generating sequence is that root must come before all its children.

Algorithm:

Base Case 1:
If ptr is NULL, then return a vector with an empty sequence.

if (ptr == NULL) {
    vector<int> seq;
    vector<vector<int> > v;
    v.push_back(seq);
    return v;
}

Base Case 2:
If ptr is a leaf node, then return a vector with a single sequence. Its Trivial that this sequence will contain only a single element, i.e. value of that node.

if (ptr -> left == NULL && ptr -> right == NULL) {
    vector<int> seq;
    seq.push_back(ptr -> val);
    vector<vector<int> > v;
    v.push_back(seq);
    return v;
}

Divide Part (this part is very simple.)
We assume that we have a function that can solve this problem, and thus we solve it for left sub tree and right sub tree.

vector<vector<int> > leftSeq  = findAllSeq(ptr -> left);
vector<vector<int> > rightSeq = findAllSeq(ptr -> right);

Merging the two solutions.(The crux is in this step.)
Till now we have two set containg distinct sequences:

i. leftSeq  - all sequences in this set will generate left subtree.
ii. rightSeq - all sequences in this set will generate right subtree.

Now each sequence in left subtree can be merged with each sequence of right subtree. While merging we should be careful that the relative order of elements is preserved. Also in each of the merged sequence we will add the value of current node in the beginning beacuse root must come before all children.

Pseudocode for Merge

vector<vector<int> > results
for all sequences L in leftSeq
    for all sequences R in rightSeq
        create a vector flags with l.size() 0's and R.size() 1's
        for all permutations of flag
            generate the corresponding merged sequence.
            append the current node's value in beginning
            add this sequence to the results.

return results. 

Explanation: Let us take a sequence, say L(of size n) from the set leftSeq, and a sequence, say R(of size m) from set rightSeq.
Now these two sequences can be merged in ^m+nC_n ways!
Proof: After merging, the new sequence will have m + n elements. As we have to maintain the relative order of elements, so firstly we will fill all n the elements from L in any of n places among total (m+n) places. After that remaining m places can be filled by elements of R. Thus we have to choose n places from (m+n) places.
To do this, lets create take a Boolean vector, say flags and fill it with n 0's and m 1's.A value of 0 represents a member from left sequence and a value of 1 represents member from right sequence. All what is left is to generate all permutations of this flags vector, which can be done with next_permutation. Now for each permutation of flags we will have a distinct merged sequence of L and R.
eg: Say L={1, 2, 3} R={4, 5}
so, n=3 and m=2
thus, we can have ³⁺²C₃ merged sequences, i.e. 10.
1.now, Initially flags = {0 0 0 1 1}, filled with 3 0's and 2 1's
this will result into this merged sequence: 1 2 3 4 5
2.after calling nextPermutation we will have
flags = {0 0 1 0 1}
and this will generate sequence: 1 2 4 3 5
3.again after calling nextPermutation we will have
flags = {0 0 1 1 0}
ans this will generate sequence: 1 2 4 5 3
and so on...

Code in C++

vector<vector<int> > findAllSeq(TreeNode *ptr)
{
    if (ptr == NULL) {
        vector<int> seq;
        vector<vector<int> > v;
        v.push_back(seq);
        return v;
    }


    if (ptr -> left == NULL && ptr -> right == NULL) {
        vector<int> seq;
        seq.push_back(ptr -> val);
        vector<vector<int> > v;
        v.push_back(seq);
        return v;
    }

    vector<vector<int> > results, left, right;
    left  = findAllSeq(ptr -> left);
    right = findAllSeq(ptr -> right);
    int size = left[0].size() + right[0].size() + 1;

    vector<bool> flags(left[0].size(), 0);
    for (int k = 0; k < right[0].size(); k++)
        flags.push_back(1);

    for (int i = 0; i < left.size(); i++) {
        for (int j = 0; j < right.size(); j++) {
            do {
                vector<int> tmp(size);
                tmp[0] = ptr -> val;
                int l = 0, r = 0;
                for (int k = 0; k < flags.size(); k++) {
                    tmp[k+1] = (flags[k]) ? right[j][r++] : left[i][l++];
                }
                results.push_back(tmp);
            } while (next_permutation(flags.begin(), flags.end()));
        }
    }

    return results;
}

Update 3rd March 2017: This solution wont work perfectly if original tree contains duplicates.

Answer 2

Here is a clear, concise and well-documented solution that I wrote for you in Python 3. I hope it helps you!

Code: bst_sequences.py

from binarytree import bst, Node


def weave_lists(first: list, second: list, results: list, prefix: list) -> None:
    """Recursively Weave the first list into the second list and append 
    it to the results list.  The prefix list grows by an element with the 
    depth of the call stack.  Ultimately, either the first or second list will 
    be exhausted and the base case will append a result."""
    # base case
    if not first or not second:
        results.append(prefix + first + second)
        return

    # recursive case
    first_head, first_tail = first[0], first[1:]
    weave_lists(first_tail, second, results, prefix + [first_head])

    second_head, second_tail = second[0], second[1:]
    weave_lists(first, second_tail, results, prefix + [second_head])


def all_sequences(root: Node) -> list:
    """Splits the tree into three lists: prefix, left, and right."""
    if root is None:
        return []

    answer = []
    prefix = [root.value]
    left = all_sequences(root.left) or [[]]
    right = all_sequences(root.right) or [[]]

    # At a minimum, left and right must be a list containing an empty list
    # for the following nested loop
    for i in range(len(left)):
        for j in range(len(right)):
            weaved = []
            weave_lists(left[i], right[j], weaved, prefix)
        answer.extend(weaved)

    return answer


if __name__ == "__main__":
    t = bst(2)
    print(t)
    solution = all_sequences(t)
    for e, item in enumerate(solution):
        print(f"{e:03}: {item}")

Sample Output

    __4
   /   \
  1     5
 / \     \
0   2     6

000: [4, 1, 0, 2, 5, 6]
001: [4, 1, 0, 5, 2, 6]
002: [4, 1, 0, 5, 6, 2]
003: [4, 1, 5, 0, 2, 6]
004: [4, 1, 5, 0, 6, 2]
005: [4, 1, 5, 6, 0, 2]
006: [4, 5, 1, 0, 2, 6]
007: [4, 5, 1, 0, 6, 2]
008: [4, 5, 1, 6, 0, 2]
009: [4, 5, 6, 1, 0, 2]
010: [4, 1, 2, 0, 5, 6]
011: [4, 1, 2, 5, 0, 6]
012: [4, 1, 2, 5, 6, 0]
013: [4, 1, 5, 2, 0, 6]
014: [4, 1, 5, 2, 6, 0]
015: [4, 1, 5, 6, 2, 0]
016: [4, 5, 1, 2, 0, 6]
017: [4, 5, 1, 2, 6, 0]
018: [4, 5, 1, 6, 2, 0]
019: [4, 5, 6, 1, 2, 0]

Process finished with exit code 0