Code is not working

#1

please tell me why passed vector is not working like pass by reference they are working like pass by value. and what should be the approach to handle the data in recursion?

#2

You can make global vectors and need not pass them in recursion . Moreover your complexity is high also . since vector.clear takes O(n) complexity .

#3

Than how to handle this global vector because if i will push_back in this vector this will contain all the elements but i need only ancestors in my vector . How to track it down.

#4

Yes… here you need to push and pop in the same if condition like

if(Current root == Required Node) {
   flag =1 ;
   return ;
}
if(!NULL){
    v.push_back(root.val);
    recursive calls();
    if(during backtrack : flag is set i.e node is found then you can return without popping) return ;
    else if ( flag is not set then just pop and return ) v.pop_back();
}

Hope this makes sense.

#5

i changed the program on the previous link i hope i wrote what you suggested use the tescases as
10
1 2 3 4 5 6 7 8 9 10
3 2 5 4 1 7 6 9 8 10
answer should be 1 6
but still it is not working please look at the code and also tell me how to track a pretucular branch in tree recursion in back tracking.

#6

This is what i am talking about

//GLOBAL VECTOR HERE
vector<node*> path_tracker;

void path(Node*root , int VALUE){
    if(root != NULL){
        if(root->val == VALUE){
            flag = 1;
            return ;
        }
        path_tracker.push_back(root);
        path(root->right , VALUE);
        if(flag == 1)return ;
        path(root->left , VALUE);
        if(flag == 1)return ;
        path_tracker.pop_back();
    }
}
1 Like
#7


still i’m not getting correct result.
input:
10
1 2 3 4 5 6 7 8 9 10
3 2 5 4 1 7 6 9 8 10
output:- 1 2 3 4 5

#8

Just made a slight change now its giving 1 6

#include <iostream>
#include<vector>
using namespace std;

class node{
    public:
    int data;
    node* left;
    node* right;
    node(int i)
    {
        data=i;
        left=nullptr;
        right=nullptr;
    }

};

void printTreePostOrder(node * root)
{
    if(root)

    {
        printTreePostOrder(root->left);
        printTreePostOrder(root->right);
        cout<<root->data<<" ";

    }
}
node* buildtreewithPreIn(int a[1000],int b[1000],int s,int e)
{
// cout<<s<<" "<<e<<endl;
if(s<=e)
{
   int i=s;
   int index=0;
for(;i<=e;i++)
if(a[0]==b[i])
{ index=i;
    break;
}
// cout<<index<<endl;
node* leftsub=buildtreewithPreIn(a+1,b,s,index-1);
node * rightsub=buildtreewithPreIn(a+(index-s)+1,b,index+1,e);
node* nd=new node(b[index]);
nd->left=leftsub;
nd->right=rightsub;
return nd;
}
    return nullptr;
}


// This code is not correctlly working

vector<node*> v;
int flag=0;
void pathToNode(node* root,int d)
{ 
    if(root)
    {
        if(root->data==d)
        {
            flag=1;
            return;
        }
        v.push_back(root);
        pathToNode(root->left,d);
        if(flag) return;
        
        pathToNode(root->right ,d);
        if(flag) return;
        v.pop_back();
    }
}

//  till here

int main() {
    // cout<<"Hello World!";
    int a[1000],b[1000];
    int n;
    cout<<"Enter no of nodes"<<endl;
    cin>>n;
    cout<<"Enter Nodes in preorder"<<endl;
    for(int i=0;i<n;i++)
    cin>>a[i];
    cout<<"Enter Nodes in Inorder"<<endl;
    for(int i=0;i<n;i++)
    cin>>b[i];
    node * root=buildtreewithPreIn(a,b,0,n-1);
    cout<<endl;
    printTreePostOrder(root);
    // vector<node* > v;
    cout<<endl;
    pathToNode(root,7);
    cout<<endl;
   
    for(auto x:v)
    cout<<x->data<<" ";
}
#9

I made a global flag.

#10

Thanks, you deserve 5 stars…

#11

Very happy to hear that :joy:

1 Like