void PrintCode(node* node , string s , int index  , struct node* root)
{
    if(node == nullptr)
    {
        return;
    }
     index = index+1;
    if(index >s.length())
    {
        return ;
    }
   

   // cout<<node->freq;
    //Leaf node reached
    if(node->left == nullptr && node->right == nullptr )
    { 
       cout<<node->data;
        node = root;
    }
    
    //Move left
    if(s[index] == '0')
    { 
        PrintCode(node->left , s, index , root);

    }else if(s[index] == '1')
    {
        PrintCode(node->right , s, index , root);
    }
   
}


void PrintLeafNode(node * node)
{
    
    if(node == nullptr)
    {
        return;
    }
    if(node->left == nullptr && node->right == nullptr)
    {    
        cout<<node->data  << " "<< node->freq << endl;
    }
    PrintLeafNode(node->left);
    PrintLeafNode(node->right);
}
void decode_huff(node * root, string s) {

    //given is root node // we can traverse root node  based on the value s
   PrintCode(root,s,-1,root);
    
}