Find all possible binary trees with given postorder Traversal

1

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
3

i think it helps you.

4

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
5

tree
tree518×540 9.58 KB

6

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

7

pre

1 Like
8

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

1 Like
9

Thanks bro.
I will check it out.

10

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 ).

11

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.

12

i’am printing all possible trees assuming preorder traversal.

13

are you getting wrong output or some error?

14 
#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
15

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