# Find all possible binary trees with given postorder Traversal

If we are given postorder traversal, then print all binary trees having this postorder traversal.
I know that it will done using recursion but unable to figure out.
Thanks!!

2 Likes

i think it helps you.

Thanks bro.
But you code is giving compilation error and i am not able to get it.
It will be a great help if you decode it.

1 Like

idk why,when i reply it is not showing some words,it is skipping them like instead of root->data it shows only data. 1 Like

Paste your code here and select the code and then press `</>` button on the top.

1 Like

Thanks bro.
I will check it out.

Need help bro.
I am getting wrong output from myside.
you are printing all possible binary trees given postorder traversal.(:right ).

bro I had stuck in this question anf i spent whole day in thinking about it.

i’am printing all possible trees assuming preorder traversal.

are you getting wrong output or some error?

``````#include <bits/stdc++.h>
using namespace std;

class Node{
public:
int data;
Node* left;
Node* right;
Node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};

void print(Node* root){
if(root == NULL)
return;
cout<<root->data<<":";
if(root->left)
cout<<"L"<<root->left->data;
if(root->right)
cout<<"R"<<root->right->data;
cout<<endl;
print(root->left);
print(root->right);
}

vector<Node*> buildAllTrees(vector<int> &v,int si,int ei){
vector<Node*> ans;
if(si > ei){
ans.push_back(NULL);
return ans;
}

if(si == ei){
ans.push_back(new Node(v[si]));
return ans;
}

for(int i = si;i<=ei;i++){
vector<Node*> l = buildAllTrees(v,si+1,i);
vector<Node*> r = buildAllTrees(v,i+1,ei);
int ans1 = l.size();
int ans2 = r.size();
for(int i = 0;i < ans1 ;i++){
Node* n = l[i];
for(int j = 0 ;j < ans2;j++){
Node* j1 = r[j];
Node* a = new Node(v[si]);
a->left = n;
a->right =  j1;
ans.push_back(a);
}
}
}
return ans;
}

int main() {
vector<int> v = {1,2,3,4,5};
vector<Node*> ans = buildAllTrees(v,0,2);
for(int i = 0 ;i < ans.size() ; i++){
print(ans[i]);
cout<<endl;
cout<<"----------------------------------------------------------"<<endl;
}
}``````
1 Like

I need printing all possible trees having postorder traversal.
Do you know how to do that.