#include <iostream>
#include <vector>
#include <string>

using namespace std;

struct Cvor {
    Cvor(char c):vrednost(c){};
    char vrednost;
    Cvor *levo = nullptr;
    Cvor *desno = nullptr;
};

/* ---- Pomocne funkcije ------- */

void LKD(Cvor *koren)
{
    if(koren != nullptr)
    {
        LKD(koren->levo);
        cout << koren->vrednost << " ";
        LKD(koren->desno);
    }
}

void KLD(Cvor *koren)
{
    if(koren != nullptr)
    {
        cout << koren->vrednost << " ";
        KLD(koren->levo);
        KLD(koren->desno);
    }
}

void LDK(Cvor* koren)
{
  if(koren != nullptr)
  {
      LDK(koren->levo);
      LDK(koren->desno);
      cout << koren->vrednost << " ";
  }

}

void oslobodi(Cvor *koren)
{
    if(koren != nullptr)
    {
        oslobodi(koren->levo);
        oslobodi(koren->desno);
        delete koren;
    }
}

Cvor* rekonstrukcija(int lkd_l, int lkd_d, int kld_l, int kld_d,
                      vector<char> &LKD, vector<char> &KLD)
{
  int i;
  Cvor* koren = new Cvor(KLD[kld_l]);
  for(i = lkd_l; i <= lkd_d; i++)
    if(LKD[i] == koren->vrednost)
      break;

  if(i > lkd_d)
  {
      cerr << "Neispravni obilasci!" << endl;
      exit(EXIT_FAILURE);
  }

  koren->levo = rekonstrukcija(lkd_l, i - 1, kld_l + 1, kld_l + i - lkd_l, LKD, KLD);
  koren->desno = rekonstrukcija(i+1, lkd_d, kld_l + i - lkd_l + 1, kld_d, LKD, KLD);
  return koren;
}


int main()
{
  vector<char> LKD;
  vector<char> KLD;
  int n;
  char c;

  cout << "Broj cvorova: ";
  cin >> n;

  if(n <= 0)
  {
      cerr << "Neispravan broj cvorova!" << endl;
      return -1;
  }

  cout << "LKD: ";
  for(int i = 0; i < n; i++)
  {
      cin >> c;
      LKD.push_back(c);
  }

  cin.get(c);

  cout << "KLD: ";
  for(int i = 0; i < n; i++)
  {
      cin >> c;
      KLD.push_back(c);
  }

  Cvor* koren = rekonstrukcija(0, n-1, 0, n-1, LKD, KLD);

  LKD(koren);
  cout << endl;
  KLD(koren);
  cout << endl;
  LDK(koren);
  cout << endl;

  oslobodi(koren);
  return 0;
}