gXa's blog

Permutations Of BST
By gXa, history, 8 years ago, In English

Hi everyone, I am trying to find all permutations of the input elements which will result in the same Binary Search tree as the one formed with the input array.

Eg: I/P: 4, 3, 1, 2, 6, 5, 7

o/p:4 , 6, 3, 7, 5, 1, 2

4, 3, 2, 1, 6, 5, 7

and so on.

I have gone through links on internet but could not code it.

I am unable to print all the permutations correctly. So, I request community to help me with logic ( if recurive function can be provided too )?

Thank You

Tags bst
  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gXa (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Hi please someone could have a look and guide me the logic to print all the permutations. I can count number of permutations by a formula but cannot print all the permutations correctly.

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it +11 Vote: I do not like it

Well heres a recursive function which I feel should solve the problem, but the time complexity is very high!
The root must always be the first element. The next element can be either its left child or right child. The element after that can be the child not taken in the previous round or the children of the current node.
poss contains the possible next elements to be added. Initially poss consists of only the root node.

void solve(vector<node> poss, vector<int> toprint)
{
    if(poss.size() == 0)
    {
        for(int i = 0; i < toprint.size(); i++)
            cout<<toprint[i]<<" ";
        cout<<endl;
        return;
    }
    
    for(int i = 0; i < poss.size(); i++)
    {
        vector<node> nxtposs;
        for(int j = 0; j < poss.size(); j++)
            if(j != i)
                nxtposs.push_back(poss[j]);
                
        if(poss[i]->left)
            nxtposs.push_back(poss[i]->left);
        if(poss[i]->right)
            nxtposs.push_back(poss[i]->right);
            
        vector<int> nxtprint = toprint;
        nxtprint.push_back(poss[i]->value);
        solve(nxtposs, nxtprint);
    }
}

How do i post code in comments lol?

→ Reply