#include <iostream>

using namespace std;
#include <cmath>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <string>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <time.h>
#include <ctime>


ofstream outf;
ifstream inf;

struct Tnode
{
    Tnode *leftchild;
    string letter;
    string code;
    Tnode *rightchild;
};

    Tnode *root;

Tnode* MyNewNode();
void insert(Tnode *, string, string);
void printTree(Tnode *);
void printTree2(Tnode *);
void printTree3(Tnode *);

int main()
{
    outf.open("results.txt");
    inf.open("morsecode.txt");

    if (!inf)
	{
		cout << "Error opening file" << endl;

		return 0;
	}

    string a, b, ary[100], ary2[100];
    char k;
    int x = 0;


	while(!inf.eof()){

        inf >> a >> b;
        ary[x] = a;
        ary2[x] = b;

        x++;

        insert(root, a, b);
	}


    printTree(root);

    outf << endl;

    printTree2(root);

    outf << endl;

    printTree3(root);


}

Tnode* MyNewNode(){

      Tnode *temp;
    temp = new Tnode;
    temp->letter.clear();
    temp->code.clear();
    temp->rightchild = NULL;
    temp->leftchild = NULL;
    return temp;

}

void insert(Tnode *c, string targ, string targ2){


    Tnode *p;
    p = NULL;

    while(c != NULL){
        p = c;

        if(targ2 < c->code){

            c = c->leftchild;

        }
        else{

            c = c->rightchild;

        }

    }

    c = MyNewNode();
    c->letter = targ;
    c->code = targ2;

     if(p == NULL){

        root = c;
    }


    if(targ2 < p->code){

        p->leftchild = c;
    }
    if(targ2 > p->code){

        p->rightchild = c;
    }



}

void printTree(Tnode *c){

    if(c == NULL){

        return;
    }

    printTree(c->leftchild);
    outf << c->letter << " ";
    printTree(c->rightchild);

}
void printTree2(Tnode *c){

    if(c == NULL){

        return;
    }

    outf << c->code << " ";
    printTree(c->leftchild);
    printTree(c->rightchild);

}

void printTree3(Tnode *c){

    if(c == NULL){

        return;
    }

    printTree(c->leftchild);
    printTree(c->rightchild);
    outf << c->letter << " ";

}