 # 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.
Please provide a code.
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.
Please provide code link.
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.
It will be great help if you share your code link.

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.