#include <iostream>

using namespace::std;

struct node {
   int x;
   node* child;
};

class linked_list_int {

   public:
   
      linked_list_int();
      ~linked_list_int();
      
      void insert(int value);
      node* search(int value);
      void destroy_list();
   
   private:
   
      node* head;
      
      void insert(int value, node* a_node);
      node* search(int value, node* a_node);
      void destroy_list(node* a_node);

};


linked_list_int::linked_list_int() {
   head=NULL;
}

linked_list_int::~linked_list_int() {
   destroy_list();
}

void linked_list_int::destroy_list() {
   destroy_list(head);
}

void linked_list_int::insert(int value) {
   if (head != NULL) {
     insert(value, head);
   }
   else {
     head=new node;
     head->x=value;
     head->child=NULL;
   }
}

node* linked_list_int::search(int value) {
   cout<<"publically searching for:"<<value<<endl;
//   node* banana=search(value,head);
//   cout<<"    publically found it at: "<<banana->x<<endl;
   return search(value, head);
}

void linked_list_int::insert(int value, node* a_node){
   if (a_node->child == NULL) {
      a_node->child=new node;
      a_node->child->x=value;
      a_node->child->child=NULL;
   }
   else {
      insert(value, a_node->child);
   }
}

node* linked_list_int::search(int value, node* a_node){
   cout<<"  privately searching for: "<<value<<endl;   
   if (a_node != NULL) {   
     if (a_node->x == value) {
       cout<<"    privately found it at: "<<a_node->x<<endl;
       return a_node;
     }
     else {
        search(value, a_node->child);
     }     
   }
   else {
     return NULL;
   }
}

void linked_list_int::destroy_list(node* a_node) {
   if (a_node != NULL) {
     destroy_list(a_node->child);
     delete a_node; 
   }
}

#include <iostream>
#include "linked_list_int.cpp"

using namespace::std;

int main(int argc, char* argv[]) {

//  cout<<"Hello, is this working?"<<endl;
  
  linked_list_int* ll=new linked_list_int;
  
  ll->insert(3);
  ll->insert(1);
  ll->insert(4);
  ll->insert(9);
  ll->insert(8);
  ll->insert(5);
  
  node* found_node;
  found_node=ll->search(4);
  
  cout<<"retrieved: "<<found_node->x<<endl;
  
  
  delete ll;
  ll=NULL;


 return 0;

}