#ifndef BINARYTREE_HPP
#define BINARYTREE_HPP

#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <stack>
#include <sstream>
#include <vector>

using namespace std;

/// @brief Nombre mínim de guions per dibuixar una aresta en el format visual.
const int MINNUMHYPENSDESCENDANT = 4;

/// @brief Nombre mínim d'espais entre subarbres en el format visual.
const int MINSPACEBETWEENSUBTREES = 4;

/**
 * @brief Classe genèrica que representa un arbre binari.
 *
 * Un arbre buit es representa fent que `left == nullptr` i `right == nullptr`.
 * En un arbre no buit, `left` i `right` apunten als subarbres esquerre i dret,
 * respectivament. Si `parent != nullptr`, llavors l'arbre actual és subarbre d'un
 * altre arbre.
 *
 * @tparam T Tipus de la informació emmagatzemada a cada node.
 */
template <typename T>
class BinaryTree {
public:
  /// Constants per gestionar els formats d'entrada/sortida.
  static const int POSTORDERFORMAT = 1;
  static const int LEFTVISUALFORMAT = 2;
  static const int VISUALFORMAT = 3;
  static const int INLINEFORMAT = 4;

  /**
   * @brief Construeix un arbre buit.
   * @pre Cert.
   * @post El paràmetre implícit representa un arbre buit.
   * @cost O(1).
   */
  BinaryTree();

  /**
   * @brief Construeix una còpia profunda d'un arbre.
   * @pre Cert.
   * @post El paràmetre implícit és una còpia profunda de `t`.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  BinaryTree(const BinaryTree<T> &t);

  /**
   * @brief Construeix un arbre amb arrel i subarbres donats.
   * @pre Cert.
   * @post El paràmetre implícit és un arbre amb arrel `root` i còpies profundes de
   *       `left` i `right` com a fills directes.
   * @cost O(n1 + n2), on n1 i n2 són els nombres de nodes de `left` i `right`.
   */
  BinaryTree(const T &root, const BinaryTree<T> &left, const BinaryTree<T> &right);

  /**
   * @brief Destrueix l'arbre i allibera tota la memòria dinàmica associada.
   * @pre Cert.
   * @post S'ha alliberat tota la memòria ocupada pels descendents del paràmetre implícit.
   * @cost O(n), on n és el nombre de nodes descendents a eliminar.
   */
  ~BinaryTree();

  /**
   * @brief Fa que l'arbre esdevingui buit.
   * @pre Cert.
   * @post El paràmetre implícit representa un arbre buit.
   * @cost O(n), on n és el nombre de nodes que contenia l'arbre.
   */
  void makeEmpty();

  /**
   * @brief Assigna una còpia profunda d'un arbre.
   * @pre Cert.
   * @post El paràmetre implícit és una còpia profunda de `t` i es retorna una referència a ell mateix.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  BinaryTree<T> &operator=(const BinaryTree<T> &t);

  /**
   * @brief Retorna una referència a l'arrel.
   * @pre El paràmetre implícit no és buit.
   * @post El resultat és una referència al valor de l'arrel del paràmetre implícit.
   * @cost O(1).
   */
  T &getRoot();

  /**
   * @brief Retorna una referència constant a l'arrel.
   * @pre El paràmetre implícit no és buit.
   * @post El resultat és una referència constant al valor de l'arrel del paràmetre implícit.
   * @cost O(1).
   */
  const T &getRoot() const;

  /**
   * @brief Retorna una referència al subarbre esquerre.
   * @pre El paràmetre implícit no és buit.
   * @post El resultat és una referència al fill esquerre del paràmetre implícit.
   * @cost O(1).
   */
  BinaryTree<T> &getLeft();

  /**
   * @brief Retorna una referència constant al subarbre esquerre.
   * @pre El paràmetre implícit no és buit.
   * @post El resultat és una referència constant al fill esquerre del paràmetre implícit.
   * @cost O(1).
   */
  const BinaryTree<T> &getLeft() const;

  /**
   * @brief Retorna una referència al subarbre dret.
   * @pre El paràmetre implícit no és buit.
   * @post El resultat és una referència al fill dret del paràmetre implícit.
   * @cost O(1).
   */
  BinaryTree<T> &getRight();

  /**
   * @brief Retorna una referència constant al subarbre dret.
   * @pre El paràmetre implícit no és buit.
   * @post El resultat és una referència constant al fill dret del paràmetre implícit.
   * @cost O(1).
   */
  const BinaryTree<T> &getRight() const;

  /**
   * @brief Indica si l'arbre és buit.
   * @pre Cert.
   * @post El resultat és cert si i només si el paràmetre implícit representa un arbre buit.
   * @cost O(1).
   */
  bool isEmpty() const;

  /**
   * @brief Indica si l'arbre té pare.
   * @pre Cert.
   * @post El resultat és cert si i només si el paràmetre implícit té pare.
   * @cost O(1).
   */
  bool hasParent() const;

  /**
   * @brief Retorna una referència al pare.
   * @pre El paràmetre implícit té pare.
   * @post El resultat és una referència al pare del paràmetre implícit.
   * @cost O(1).
   */
  BinaryTree<T> &getParent();

  /**
   * @brief Retorna una referència constant al pare.
   * @pre El paràmetre implícit té pare.
   * @post El resultat és una referència constant al pare del paràmetre implícit.
   * @cost O(1).
   */
  const BinaryTree<T> &getParent() const;

  /**
   * @brief Fixa el format d'entrada del subarbre actual i de tots els seus descendents.
   * @pre `format` és un format vàlid.
   * @post El camp `inputformat` del paràmetre implícit i de tots els seus descendents val `format`.
   * @cost O(n), on n és el nombre de nodes del subarbre actual.
   */
  void setInputFormat(int format);

  /**
   * @brief Fixa el format de sortida del subarbre actual i de tots els seus descendents.
   * @pre `format` és un format vàlid.
   * @post El camp `outputformat` del paràmetre implícit i de tots els seus descendents val `format`.
   * @cost O(n), on n és el nombre de nodes del subarbre actual.
   */
  void setOutputFormat(int format);

  /**
   * @brief Fixa alhora el format d'entrada i el de sortida.
   * @pre `format` és un format vàlid.
   * @post El camp `inputformat` i el camp `outputformat` del paràmetre implícit i de tots els seus descendents valen `format`.
   * @cost O(n), on n és el nombre de nodes del subarbre actual.
   */
  void setInputOutputFormat(int format);

  /**
   * @brief Consulta el format d'entrada actual.
   * @pre Cert.
   * @post El resultat és el format d'entrada actual del paràmetre implícit.
   * @cost O(1).
   */
  int getInputFormat() const;

  /**
   * @brief Consulta el format de sortida actual.
   * @pre Cert.
   * @post El resultat és el format de sortida actual del paràmetre implícit.
   * @cost O(1).
   */
  int getOutputFormat() const;

  /**
   * @brief Escriu un arbre en un flux de sortida.
   * @pre Cert.
   * @post S'ha escrit a `os` una representació de `t` segons el seu format de sortida.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  template <class U>
  friend std::ostream &operator<<(std::ostream &os, const BinaryTree<U> &t);

  /**
   * @brief Llegeix un arbre d'un flux d'entrada.
   * @pre `is` conté una representació correcta d'un arbre segons el format d'entrada de `t`.
   * @post `t` pren el valor de l'arbre llegit de `is`.
   * @cost O(n), on n és el nombre de nodes de l'arbre llegit.
   */
  template <class U>
  friend std::istream &operator>>(std::istream &is, BinaryTree<U> &t);
  
	void minAtDepth(vector<T>& result) const;

private:
  BinaryTree *left;
  BinaryTree *right;
  BinaryTree *parent;
  T root;
  int inputformat;
  int outputformat;

  /**
   * @brief Elimina profundament els dos fills directes.
   * @pre Cert.
   * @post S'ha alliberat la memòria apuntada inicialment per `left` i `right`, i tots dos camps valen `nullptr`.
   * @cost O(n), on n és el nombre total de nodes dels subarbres fills.
   */
  void deleteChildren();

  /**
   * @brief Comprova que un codi de format sigui vàlid.
   * @pre Cert.
   * @post Si `format` és invàlid, el programa acaba amb error; altrament no modifica res.
   * @cost O(1).
   */
  static void checkFormat(int format);

  /**
   * @brief Fa una còpia profunda d'un arbre i n'assigna el pare.
   * @pre Cert.
   * @post El resultat apunta a una còpia profunda de `t` amb pare `p`.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  static BinaryTree<T> *clone(const BinaryTree<T> &t, BinaryTree<T> *p);

  /**
   * @brief Mostra un missatge d'error d'entrada/sortida i acaba el programa.
   * @pre Cert.
   * @post El programa acaba mostrant el missatge `s`.
   * @cost O(|s|).
   */
  static void dieInputOutputBinaryTree(string s);

  /**
   * @brief Mostra l'error de format incorrecte d'arbre i acaba el programa.
   * @pre Cert.
   * @post El programa acaba mostrant el missatge d'error corresponent.
   * @cost O(1).
   */
  static void dieWrongFormatTree();

  /**
   * @brief Comprova una condició de format.
   * @pre Cert.
   * @post Si `condition` és falsa, el programa acaba amb error; altrament no modifica res.
   * @cost O(1).
   */
  static void checkFormatCondition(bool condition);

  /**
   * @brief Retorna la primera posició no blanca d'una cadena.
   * @pre Cert.
   * @post El resultat és la primera posició de `s` que no conté un espai en blanc; si no n'hi ha cap, retorna `s.size()`.
   * @cost O(|s|).
   */
  static int firstNonBlankPosInString(const string &s);

  /**
   * @brief Retorna la darrera posició no blanca d'una cadena.
   * @pre Cert.
   * @post El resultat és la darrera posició de `s` que no conté un espai en blanc; si no n'hi ha cap, retorna `-1`.
   * @cost O(|s|).
   */
  static int lastNonBlankPosInString(const string &s);

  /**
   * @brief Converteix un valor a cadena.
   * @pre El valor es pot escriure en un flux sense generar espais en blanc.
   * @post El resultat és una cadena que representa `value`.
   * @cost O(m), on m és la longitud de la cadena resultant.
   */
  static string value2string(const T &value);

  /**
   * @brief Converteix una cadena en un valor.
   * @pre `s` representa correctament un valor de tipus `T`.
   * @post `value` pren el valor representat per `s`.
   * @cost O(|s|).
   */
  static void string2value(const string &s, T &value);

  /**
   * @brief Insereix un prefix a totes les cadenes d'un vector.
   * @pre Cert.
   * @post Tots els elements de `v` han estat prefixats amb `prefix`.
   * @cost O(k), on k és la suma de longituds de les cadenes resultants.
   */
  static void insertPrefixVectorString(string prefix, vector<string> &v);

  /**
   * @brief Insereix un nombre d'espais inicials a totes les cadenes d'un vector.
   * @pre `space >= 0`.
   * @post Tots els elements de `v` han estat prefixats amb `space` espais.
   * @cost O(k), on k és la suma de longituds de les cadenes resultants.
   */
  static void insertSpaceVectorString(int space, vector<string> &v);

  /**
   * @brief Obté la posició central aproximada de l'arrel dins d'una línia de dibuix.
   * @pre Cert.
   * @post El resultat és la posició associada a l'arrel dins de `s`.
   * @cost O(|s|).
   */
  static int obtainRootPositionInString(const string &s);

  /**
   * @brief Compta el nombre de nodes d'un arbre.
   * @pre Cert.
   * @post El resultat és el nombre de nodes de `t`.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  static int countNumberNodes(const BinaryTree<T> &t);

  /**
   * @brief Llegeix un arbre en format postordre.
   * @pre `is` conté una representació correcta d'un arbre en format postordre.
   * @post `t` pren el valor de l'arbre llegit.
   * @cost O(n), on n és el nombre de nodes llegits.
   */
  static void readBinaryTreePostOrder(std::istream &is, BinaryTree<T> &t);

  /**
   * @brief Escriu recursivament un arbre en format postordre.
   * @pre Cert.
   * @post S'ha escrit a `os` la representació postordre del subarbre `t`, sense escriure'n la capçalera de nombre de nodes.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  static void writeBinaryTreePostOrderRec(std::ostream &os, const BinaryTree<T> &t);

  /**
   * @brief Escriu un arbre en format postordre.
   * @pre Cert.
   * @post S'ha escrit a `os` la representació completa de `t` en format postordre.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  static void writeBinaryTreePostOrder(std::ostream &os, const BinaryTree<T> &t);

  /**
   * @brief Llegeix recursivament un arbre tokenitzat en format inline.
   * @pre `vtoken` conté una tokenització correcta d'un arbre inline i `itoken` apunta al primer token pendent.
   * @post `t` pren el valor de l'arbre llegit i `itoken` apunta al primer token no consumit.
   * @cost O(n), on n és el nombre de tokens consumits.
   */
  static void readStringTree(int &itoken, const std::vector<std::pair<std::string, std::string> > &vtoken, BinaryTree<T> &t);

  /**
   * @brief Llegeix un arbre en format inline a partir d'una cadena.
   * @pre `s` conté una representació correcta d'un arbre inline.
   * @post `t` pren el valor de l'arbre llegit.
   * @cost O(|s|).
   */
  static void readStringTree(const std::string &s, BinaryTree<T> &t);

  /**
   * @brief Escriu recursivament un arbre en format inline.
   * @pre Cert.
   * @post S'ha escrit a `os` la representació inline del subarbre `t`.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  static void writeStringTreeRec(std::ostream &os, const BinaryTree<T> &t);

  /**
   * @brief Escriu un arbre en format inline.
   * @pre Cert.
   * @post S'ha escrit a `os` la representació inline de `t`.
   * @cost O(n), on n és el nombre de nodes de `t`.
   */
  static void writeStringTree(std::ostream &os, const BinaryTree<T> &t);

  /**
   * @brief Llegeix recursivament un arbre en format visual cap a l'esquerra.
   * @pre `is` conté una representació correcta a partir de la columna `j`.
   * @post `t` pren el valor del subarbre llegit.
   * @cost O(n), on n és el nombre de nodes del subarbre llegit.
   */
  static void readLeftVisualFormatRec(istream &is, int j, BinaryTree<T> &t);

  /**
   * @brief Llegeix un arbre en format visual cap a l'esquerra.
   * @pre `is` conté una representació correcta d'un arbre en aquest format.
   * @post `t` pren el valor de l'arbre llegit.
   * @cost O(n), on n és el nombre de nodes llegits.
   */
  static void readLeftVisualFormat(istream &is, BinaryTree<T> &t);

  /**
   * @brief Genera les línies del dibuix en format visual cap a l'esquerra.
   * @pre Cert.
   * @post El resultat és un vector amb la representació visual del subarbre `t` cap a l'esquerra.
   * @cost O(n + k), on n és el nombre de nodes i k la mida total del text generat.
   */
  static vector<string> generateLeftVisualFormatRec(const BinaryTree<T> &t);

  /**
   * @brief Llegeix recursivament un arbre en format visual complet.
   * @pre `v` conté una representació correcta del subarbre delimitat per `i` i `j`.
   * @post `t` pren el valor del subarbre llegit.
   * @cost O(n + k), depenent del subarbre processat i del text inspeccionat.
   */
  static void readVisualFormatRec(const vector<string> &v, int i, int j, BinaryTree<T> &t);

  /**
   * @brief Llegeix un arbre en format visual complet.
   * @pre `v` conté una representació correcta d'un arbre en format visual.
   * @post `t` pren el valor de l'arbre llegit.
   * @cost O(n + k), on n és el nombre de nodes i k la mida del text processat.
   */
  static void readVisualFormat(const vector<string> &v, BinaryTree<T> &t);

  /**
   * @brief Genera recursivament les línies del dibuix en format visual complet.
   * @pre Cert.
   * @post El resultat és un vector amb la representació visual del subarbre `t`.
   * @cost O(n + k), on n és el nombre de nodes i k la mida total del text generat.
   */
  static vector<string> generateVisualFormatRec(const BinaryTree<T> &t);

  /**
   * @brief Genera les línies del dibuix en format visual complet.
   * @pre Cert.
   * @post El resultat és un vector amb la representació visual de `t`.
   * @cost O(n + k), on n és el nombre de nodes i k la mida total del text generat.
   */
  static vector<string> generateVisualFormat(const BinaryTree<T> &t);
};

template <typename T>
BinaryTree<T>::BinaryTree() {
  left = nullptr;
  right = nullptr;
  parent = nullptr;
  inputformat = INLINEFORMAT;
  outputformat = INLINEFORMAT;
}

template <typename T>
BinaryTree<T>::BinaryTree(const BinaryTree<T> &t) {
  // Fita de les crides recursives a clone: nombre de nodes de l'arbre a clonar.
  parent = nullptr;
  inputformat = t.inputformat;
  outputformat = t.outputformat;

  if (t.isEmpty()) {
    left = nullptr;
    right = nullptr;
  } else {
    root = t.root;
    // HI: clone(t.getLeft(), this) retorna una còpia profunda del fill esquerre amb pare this.
    // Fita: nombre de nodes de t.getLeft() < nombre de nodes de t.
    left = clone(t.getLeft(), this);
    // HI: clone(t.getRight(), this) retorna una còpia profunda del fill dret amb pare this.
    // Fita: nombre de nodes de t.getRight() < nombre de nodes de t.
    right = clone(t.getRight(), this);
  }
}

template <typename T>
BinaryTree<T>::BinaryTree(const T &root, const BinaryTree<T> &left, const BinaryTree<T> &right) {
  this->root = root;
  this->left = new BinaryTree<T>(left);
  this->right = new BinaryTree<T>(right);
  this->left->parent = this;
  this->right->parent = this;
  this->parent = nullptr;
  inputformat = INLINEFORMAT;
  outputformat = INLINEFORMAT;
}

template <typename T>
BinaryTree<T>::~BinaryTree() {
  deleteChildren();
}

template <typename T>
void BinaryTree<T>::deleteChildren() {
  if (left != nullptr) {
    delete left;
  }
  if (right != nullptr) {
    delete right;
  }
  left = nullptr;
  right = nullptr;
}

template <typename T>
void BinaryTree<T>::checkFormat(int format) {
  bool valid = format == POSTORDERFORMAT or format == LEFTVISUALFORMAT or format == VISUALFORMAT or format == INLINEFORMAT;
  if (not valid) {
    std::cerr << "ERROR: wrong tree format" << std::endl;
    exit(1);
  }
}

template <typename T>
BinaryTree<T> *BinaryTree<T>::clone(const BinaryTree<T> &t, BinaryTree<T> *p) {
  // Fita de la funció recursiva: nombre de nodes de t.
  BinaryTree<T> *node = new BinaryTree<T>();
  node->parent = p;

  if (p != nullptr) {
    node->inputformat = p->inputformat;
    node->outputformat = p->outputformat;
  } else {
    node->inputformat = t.inputformat;
    node->outputformat = t.outputformat;
  }

  if (t.isEmpty()) {
    node->left = nullptr;
    node->right = nullptr;
  } else {
    node->root = t.root;
    // HI: clone(t.getLeft(), node) retorna una còpia profunda del fill esquerre amb pare node.
    // Fita: nombre de nodes de t.getLeft() < nombre de nodes de t.
    node->left = clone(t.getLeft(), node);
    // HI: clone(t.getRight(), node) retorna una còpia profunda del fill dret amb pare node.
    // Fita: nombre de nodes de t.getRight() < nombre de nodes de t.
    node->right = clone(t.getRight(), node);
  }

  return node;
}

template <typename T>
void BinaryTree<T>::makeEmpty() {
  if (not isEmpty()) {
    delete left;
    delete right;
    left = nullptr;
    right = nullptr;
  }
}

template <typename T>
BinaryTree<T> &BinaryTree<T>::operator=(const BinaryTree<T> &t) {
  if (this != &t) {
    BinaryTree<T> *oldParent = parent;
    int oldInputFormat = inputformat;
    int oldOutputFormat = outputformat;

    BinaryTree<T> *newLeft = nullptr;
    BinaryTree<T> *newRight = nullptr;
    T newRoot;
    bool empty = t.isEmpty();

    if (not empty) {
      newRoot = t.root;
      // HI: clone(t.getLeft(), this) retorna una còpia profunda del fill esquerre amb pare this.
      // Fita: nombre de nodes de t.getLeft() < nombre de nodes de t.
      newLeft = clone(t.getLeft(), this);
      // HI: clone(t.getRight(), this) retorna una còpia profunda del fill dret amb pare this.
      // Fita: nombre de nodes de t.getRight() < nombre de nodes de t.
      newRight = clone(t.getRight(), this);
    }

    deleteChildren();
    parent = oldParent;
    inputformat = oldInputFormat;
    outputformat = oldOutputFormat;

    if (empty) {
      left = nullptr;
      right = nullptr;
    } else {
      root = newRoot;
      left = newLeft;
      right = newRight;
    }
  }
  return *this;
}

template <typename T>
T &BinaryTree<T>::getRoot() {
  if (isEmpty()) {
    std::cout << "ERROR - Operation 'getRoot' over an empty tree." << std::endl;
    exit(1);
  }
  return root;
}

template <typename T>
const T &BinaryTree<T>::getRoot() const {
  if (isEmpty()) {
    std::cout << "ERROR - Operation 'getRoot' over an empty tree." << std::endl;
    exit(1);
  }
  return root;
}

template <typename T>
BinaryTree<T> &BinaryTree<T>::getLeft() {
  if (isEmpty()) {
    std::cout << "ERROR - Operation 'getLeft' over an empty tree." << std::endl;
    exit(1);
  }
  return *left;
}

template <typename T>
const BinaryTree<T> &BinaryTree<T>::getLeft() const {
  if (isEmpty()) {
    std::cout << "ERROR - Operation 'getLeft' over an empty tree." << std::endl;
    exit(1);
  }
  return *left;
}

template <typename T>
BinaryTree<T> &BinaryTree<T>::getRight() {
  if (isEmpty()) {
    std::cout << "ERROR - Operation 'right' over an empty tree." << std::endl;
    exit(1);
  }
  return *right;
}

template <typename T>
const BinaryTree<T> &BinaryTree<T>::getRight() const {
  if (isEmpty()) {
    std::cout << "ERROR - Operation 'right' over an empty tree." << std::endl;
    exit(1);
  }
  return *right;
}

template <typename T>
bool BinaryTree<T>::isEmpty() const {
  bool empty = (left == nullptr) and (right == nullptr);
  return empty;
}

template <typename T>
bool BinaryTree<T>::hasParent() const {
  bool result = parent != nullptr;
  return result;
}

template <typename T>
BinaryTree<T> &BinaryTree<T>::getParent() {
  if (not hasParent()) {
    std::cout << "ERROR - Operation 'getParent' over a tree without parent." << std::endl;
    exit(1);
  }
  return *parent;
}

template <typename T>
const BinaryTree<T> &BinaryTree<T>::getParent() const {
  if (not hasParent()) {
    std::cout << "ERROR - Operation 'getParent' over a tree without parent." << std::endl;
    exit(1);
  }
  return *parent;
}

template <typename T>
void BinaryTree<T>::setInputFormat(int format) {
  // Fita de la funció recursiva: nombre de nodes del subarbre actual.
  checkFormat(format);
  inputformat = format;
  if (left != nullptr) {
    // HI: left->setInputFormat(format) fixa correctament el format d'entrada a tot el subarbre esquerre.
    // Fita: nombre de nodes de left < nombre de nodes del subarbre actual.
    left->setInputFormat(format);
  }
  if (right != nullptr) {
    // HI: right->setInputFormat(format) fixa correctament el format d'entrada a tot el subarbre dret.
    // Fita: nombre de nodes de right < nombre de nodes del subarbre actual.
    right->setInputFormat(format);
  }
}

template <typename T>
void BinaryTree<T>::setOutputFormat(int format) {
  // Fita de la funció recursiva: nombre de nodes del subarbre actual.
  checkFormat(format);
  outputformat = format;
  if (left != nullptr) {
    // HI: left->setOutputFormat(format) fixa correctament el format de sortida a tot el subarbre esquerre.
    // Fita: nombre de nodes de left < nombre de nodes del subarbre actual.
    left->setOutputFormat(format);
  }
  if (right != nullptr) {
    // HI: right->setOutputFormat(format) fixa correctament el format de sortida a tot el subarbre dret.
    // Fita: nombre de nodes de right < nombre de nodes del subarbre actual.
    right->setOutputFormat(format);
  }
}

template <typename T>
void BinaryTree<T>::setInputOutputFormat(int format) {
  setInputFormat(format);
  setOutputFormat(format);
}

template <typename T>
int BinaryTree<T>::getInputFormat() const {
  return inputformat;
}

template <typename T>
int BinaryTree<T>::getOutputFormat() const {
  return outputformat;
}

template <typename T>
void BinaryTree<T>::dieInputOutputBinaryTree(string s) {
  std::cerr << s << std::endl;
  exit(1);
}

template <typename T>
void BinaryTree<T>::dieWrongFormatTree() {
  dieInputOutputBinaryTree("Error: Wrong format input tree");
}

template <typename T>
void BinaryTree<T>::checkFormatCondition(bool condition) {
  if (not condition) {
    dieWrongFormatTree();
  }
}

template <typename T>
int BinaryTree<T>::firstNonBlankPosInString(const string &s) {
  int i = 0;
  // Inv: tots els caràcters de posició < i són espais en blanc.
  while (i < int(s.size()) and s[i] == ' ') {
    ++i;
    // Fita: int(s.size()) - i.
  }
  return i;
}

template <typename T>
int BinaryTree<T>::lastNonBlankPosInString(const string &s) {
  int i = int(s.size()) - 1;
  // Inv: tots els caràcters de posició > i són espais en blanc.
  while (i >= 0 and s[i] == ' ') {
    --i;
    // Fita: i + 1.
  }
  return i;
}

template <typename T>
string BinaryTree<T>::value2string(const T &value) {
  ostringstream mycout;
  if (not (mycout << value)) {
    dieInputOutputBinaryTree("Error: We could not transform a value into a string");
  }
  string s = mycout.str();
  if (int(s.size()) == 0) {
    dieInputOutputBinaryTree("Error: length 0 is not allowed for strings describing values");
  }
  int i = 0;
  // Inv: tots els caràcters de les posicions [0..i-1] són diferents d'un espai.
  while (i < int(s.size())) {
    if (s[i] == ' ') {
      dieInputOutputBinaryTree("Error: white spaces are not allowed for strings describing values");
    }
    ++i;
    // Fita: int(s.size()) - i.
  }
  return s;
}

template <typename T>
void BinaryTree<T>::string2value(const string &s, T &value) {
  istringstream mycin(s);
  if (not (mycin >> value)) {
    dieInputOutputBinaryTree("Error: We could not transform a string into a value");
  }
  string rest;
  if (mycin >> rest) {
    dieInputOutputBinaryTree("Error: We could not transform a string into a value");
  }
}

template <typename T>
void BinaryTree<T>::insertPrefixVectorString(string prefix, vector<string> &v) {
  int i = 0;
  // Inv: per a tot k < i, v[k] ja ha estat prefixada amb prefix; per a tot k >= i, v[k] conserva el valor original.
  while (i < int(v.size())) {
    v[i] = prefix + v[i];
    ++i;
    // Fita: int(v.size()) - i.
  }
}

template <typename T>
void BinaryTree<T>::insertSpaceVectorString(int space, vector<string> &v) {
  insertPrefixVectorString(string(space, ' '), v);
}

template <typename T>
int BinaryTree<T>::obtainRootPositionInString(const string &s) {
  int position = (firstNonBlankPosInString(s) + int(s.size()) - 1) / 2;
  return position;
}

template <class T>
int BinaryTree<T>::countNumberNodes(const BinaryTree<T> &t) {
  // Fita de la funció recursiva: nombre de nodes de t.
  int result = 0;
  if (not t.isEmpty()) {
    // HI: countNumberNodes(t.getLeft()) retorna el nombre de nodes del subarbre esquerre.
    // Fita: nombre de nodes de t.getLeft() < nombre de nodes de t.
    int leftCount = countNumberNodes(t.getLeft());
    // HI: countNumberNodes(t.getRight()) retorna el nombre de nodes del subarbre dret.
    // Fita: nombre de nodes de t.getRight() < nombre de nodes de t.
    int rightCount = countNumberNodes(t.getRight());
    result = 1 + leftCount + rightCount;
  }
  return result;
}

template <class T>
void BinaryTree<T>::readBinaryTreePostOrder(std::istream &is, BinaryTree<T> &t) {
  int size;
  std::stack<BinaryTree<T>> s;

  is >> size;
  // Inv: la pila s conté exactament els subarbres construïts a partir dels registres ja llegits que encara no s'han connectat definitivament, i size és el nombre de registres pendents de processar.
  while (size > 0) {
    T node;
    int numchildren;
    is >> node >> numchildren;
    if (numchildren == 0) {
      s.push(BinaryTree<T>(node, BinaryTree<T>(), BinaryTree<T>()));
    } else if (numchildren == -1) {
      BinaryTree<T> leftTree = s.top();
      s.pop();
      s.push(BinaryTree<T>(node, leftTree, BinaryTree<T>()));
    } else if (numchildren == 1) {
      BinaryTree<T> rightTree = s.top();
      s.pop();
      s.push(BinaryTree<T>(node, BinaryTree<T>(), rightTree));
    } else {
      BinaryTree<T> rightTree = s.top();
      s.pop();
      BinaryTree<T> leftTree = s.top();
      s.pop();
      s.push(BinaryTree<T>(node, leftTree, rightTree));
    }
    --size;
    // Fita: size.
  }
  if (not s.empty()) {
    t = s.top();
  }
}

template <class T>
void BinaryTree<T>::writeBinaryTreePostOrderRec(std::ostream &os, const BinaryTree<T> &t) {
  // Fita de la funció recursiva: nombre de nodes de t.
  if (not t.isEmpty()) {
    // HI: writeBinaryTreePostOrderRec(os, t.getLeft()) escriu correctament el subarbre esquerre en postordre.
    // Fita: nombre de nodes de t.getLeft() < nombre de nodes de t.
    writeBinaryTreePostOrderRec(os, t.getLeft());
    // HI: writeBinaryTreePostOrderRec(os, t.getRight()) escriu correctament el subarbre dret en postordre.
    // Fita: nombre de nodes de t.getRight() < nombre de nodes de t.
    writeBinaryTreePostOrderRec(os, t.getRight());
    os << t.getRoot() << " ";
    if (t.getLeft().isEmpty() and t.getRight().isEmpty()) {
      os << 0;
    } else if (t.getLeft().isEmpty()) {
      os << 1;
    } else if (t.getRight().isEmpty()) {
      os << -1;
    } else {
      os << 2;
    }
    os << endl;
  }
}

template <class T>
void BinaryTree<T>::writeBinaryTreePostOrder(std::ostream &os, const BinaryTree<T> &t) {
  os << countNumberNodes(t) << endl;
  writeBinaryTreePostOrderRec(os, t);
}

template <typename T>
void BinaryTree<T>::readStringTree(int &itoken, const std::vector<std::pair<std::string, std::string>> &vtoken, BinaryTree<T> &t) {
  // Fita de la funció recursiva: nombre de tokens pendents, int(vtoken.size()) - itoken.
  if (itoken >= int(vtoken.size()) or vtoken[itoken].first != "value") {
    t = BinaryTree<T>();
  } else {
    std::istringstream mycin(vtoken[itoken].second);
    T value;
    mycin >> value;
    t = BinaryTree<T>(value, BinaryTree<T>(), BinaryTree<T>());
    ++itoken;

    if (itoken < int(vtoken.size()) and vtoken[itoken].first == "(") {
      ++itoken;
      // HI: readStringTree(itoken, vtoken, t.getLeft()) llegeix correctament el subarbre esquerre i actualitza itoken.
      // Fita: en la crida recursiva, int(vtoken.size()) - itoken disminueix.
      readStringTree(itoken, vtoken, t.getLeft());
      if (itoken >= int(vtoken.size()) or vtoken[itoken].first != ",") {
        t.getRight() = BinaryTree<T>();
        if (itoken < int(vtoken.size()) and vtoken[itoken].first == ")") {
          ++itoken;
        }
      } else {
        ++itoken;
        // HI: readStringTree(itoken, vtoken, t.getRight()) llegeix correctament el subarbre dret i actualitza itoken.
        // Fita: en la crida recursiva, int(vtoken.size()) - itoken disminueix.
        readStringTree(itoken, vtoken, t.getRight());
        if (itoken < int(vtoken.size()) and vtoken[itoken].first == ")") {
          ++itoken;
        }
      }
    }
  }
}

template <typename T>
void BinaryTree<T>::readStringTree(const std::string &s, BinaryTree<T> &t) {
  std::vector<std::pair<std::string, std::string>> vtoken;
  int iant = 0;
  int i = 0;
  // Inv: vtoken conté exactament els tokens complets de s[0..i-1], i iant marca l'inici del fragment pendent de convertir en token de valor.
  while (i < int(s.size())) {
    if (s[i] == ',' or s[i] == '(' or s[i] == ')') {
      if (iant < i) {
        vtoken.push_back(std::pair<std::string, std::string>("value", s.substr(iant, i - iant)));
      }
      iant = i + 1;
      vtoken.push_back(std::pair<std::string, std::string>(std::string(1, s[i]), ""));
    }
    ++i;
    // Fita: int(s.size()) - i.
  }
  if (iant < int(s.size())) {
    vtoken.push_back(std::pair<std::string, std::string>("value", s.substr(iant)));
  }
  int itoken = 0;
  // HI: readStringTree(itoken, vtoken, t) llegeix correctament l'arbre codificat pels tokens restants.
  // Fita: en la crida recursiva, int(vtoken.size()) - itoken disminueix.
  readStringTree(itoken, vtoken, t);
}

template <typename T>
void BinaryTree<T>::writeStringTreeRec(std::ostream &os, const BinaryTree<T> &t) {
  // Fita de la funció recursiva: nombre de nodes de t.
  if (not t.isEmpty()) {
    os << t.getRoot();
    const BinaryTree<T> &leftTree = t.getLeft();
    const BinaryTree<T> &rightTree = t.getRight();
    if (not (leftTree.isEmpty() and rightTree.isEmpty())) {
      os << "(";
      // HI: writeStringTreeRec(os, leftTree) escriu correctament el subarbre esquerre en format inline.
      // Fita: nombre de nodes de leftTree < nombre de nodes de t.
      writeStringTreeRec(os, leftTree);
      os << ",";
      // HI: writeStringTreeRec(os, rightTree) escriu correctament el subarbre dret en format inline.
      // Fita: nombre de nodes de rightTree < nombre de nodes de t.
      writeStringTreeRec(os, rightTree);
      os << ")";
    }
  }
}

template <typename T>
void BinaryTree<T>::writeStringTree(std::ostream &os, const BinaryTree<T> &t) {
  if (t.isEmpty()) {
    os << "()";
  } else {
    writeStringTreeRec(os, t);
  }
}

template <typename T>
void BinaryTree<T>::readLeftVisualFormatRec(istream &is, int j, BinaryTree<T> &t) {
  // Fita de la funció recursiva: nombre de línies pendents de llegir corresponents al subarbre actual.
  string line;
  getline(is, line);
  string s = line.substr(j);
  if (s == ".") {
    t = BinaryTree<T>();
  } else {
    if (int(s.size()) == 0 or s[0] != '[') {
      dieInputOutputBinaryTree("Error: Wrong format for input tree");
    }
    if (s[int(s.size()) - 1] != ']') {
      dieInputOutputBinaryTree("Error: Wrong format for input tree");
    }
    T value;
    string2value(s.substr(1, int(s.size()) - 2), value);
    t = BinaryTree<T>(value, BinaryTree<T>(), BinaryTree<T>());
    // HI: readLeftVisualFormatRec(is, j+4, t.getRight()) llegeix correctament el subarbre dret.
    // Fita: en la crida recursiva, el nombre de línies pendents del subarbre dret és menor que el del subarbre actual.
    readLeftVisualFormatRec(is, j + 4, t.getRight());
    // HI: readLeftVisualFormatRec(is, j+4, t.getLeft()) llegeix correctament el subarbre esquerre.
    // Fita: en la crida recursiva, el nombre de línies pendents del subarbre esquerre és menor que el del subarbre actual.
    readLeftVisualFormatRec(is, j + 4, t.getLeft());
  }
}

template <typename T>
void BinaryTree<T>::readLeftVisualFormat(istream &is, BinaryTree<T> &t) {
  readLeftVisualFormatRec(is, 0, t);
}

template <typename T>
vector<string> BinaryTree<T>::generateLeftVisualFormatRec(const BinaryTree<T> &t) {
  // Fita de la funció recursiva: nombre de nodes de t.
  vector<string> result;
  if (t.isEmpty()) {
    result.push_back(".");
  } else {
    string rootstring = value2string(t.getRoot());
    // HI: generateLeftVisualFormatRec(t.getLeft()) genera correctament la representació visual esquerra del subarbre esquerre.
    // Fita: nombre de nodes de t.getLeft() < nombre de nodes de t.
    vector<string> leftresult = generateLeftVisualFormatRec(t.getLeft());
    // HI: generateLeftVisualFormatRec(t.getRight()) genera correctament la representació visual esquerra del subarbre dret.
    // Fita: nombre de nodes de t.getRight() < nombre de nodes de t.
    vector<string> rightresult = generateLeftVisualFormatRec(t.getRight());
    result.push_back("[" + rootstring + "]");

    int i = 0;
    // Inv: s'han afegit correctament a result les primeres i línies de rightresult en format visual esquerra.
    while (i < int(rightresult.size())) {
      if (i == 0) {
        result.push_back(" \\__" + rightresult[i]);
      } else {
        result.push_back(" |  " + rightresult[i]);
      }
      ++i;
      // Fita: int(rightresult.size()) - i.
    }

    i = 0;
    // Inv: s'han afegit correctament a result les primeres i línies de leftresult en format visual esquerra.
    while (i < int(leftresult.size())) {
      if (i == 0) {
        result.push_back(" \\__" + leftresult[i]);
      } else {
        result.push_back("    " + leftresult[i]);
      }
      ++i;
      // Fita: int(leftresult.size()) - i.
    }
  }
  return result;
}

template <typename T>
void BinaryTree<T>::readVisualFormatRec(const vector<string> &v, int i, int j, BinaryTree<T> &t) {
  // Fita de la funció recursiva: nombre de línies pendents de processar del subarbre actual.
  bool emptyCell = i < 0 or int(v.size()) <= i or j < 0 or int(v[i].size()) <= j or v[i][j] == ' ';
  if (emptyCell) {
    t = BinaryTree<T>();
  } else {
    const string &line = v[i];
    int jini = j;
    // Inv: tots els caràcters de line a l'interval [jini, j-1] formen part del mateix token i no s'ha arribat al seu inici.
    while (jini > 0 and line[jini - 1] != ' ') {
      --jini;
      // Fita: jini.
    }
    int jend = j;
    // Inv: tots els caràcters de line a l'interval [j, jend] formen part del mateix token i no s'ha arribat al seu final.
    while (jend + 1 <= int(line.size()) - 1 and line[jend + 1] != ' ') {
      ++jend;
      // Fita: int(line.size()) - 1 - jend.
    }

    string rootstring = line.substr(jini, jend - jini + 1);
    T rootValue;
    string2value(rootstring, rootValue);
    t = BinaryTree<T>(rootValue, BinaryTree<T>(), BinaryTree<T>());

    if (int(v.size()) > i + 1) {
      const string &linedown = v[i + 1];
      int jdown = jini;
      // Inv: totes les posicions de linedown a [jini, jdown-1] són espais.
      while (jdown < int(linedown.size()) and jdown <= jend and linedown[jdown] == ' ') {
        ++jdown;
        // Fita: min(int(linedown.size()), jend + 1) - jdown.
      }
      if (not (int(linedown.size()) <= jdown or jend < jdown)) {
        checkFormatCondition(linedown[jdown] == '|');
        checkFormatCondition(i + 3 < int(v.size()));
        const string &line2down = v[i + 2];
        const string &line3down = v[i + 3];

        int jleft = jdown - 1;
        if (jleft >= 0 and jleft < int(line2down.size()) and line2down[jleft] == '-') {
          // Inv: totes les posicions de line2down a [jleft+1, jdown-1] contenen '-'.
          while (jleft >= 0 and line2down[jleft] == '-') {
            --jleft;
            // Fita: jleft + 1.
          }
          checkFormatCondition(0 <= jleft and jleft < int(line3down.size()) and line3down[jleft] == '|');
          // HI: readVisualFormatRec(v, i+4, jleft, t.getLeft()) llegeix correctament el subarbre esquerre.
          // Fita: en la crida recursiva, el nombre de línies pendents de processar del subarbre esquerre és menor que el del subarbre actual.
          readVisualFormatRec(v, i + 4, jleft, t.getLeft());
        }

        int jright = jdown + 1;
        if (jright < int(line2down.size()) and line2down[jright] == '-') {
          // Inv: totes les posicions de line2down a [jdown+1, jright-1] contenen '-'.
          while (jright >= 0 and jright < int(line2down.size()) and line2down[jright] == '-') {
            ++jright;
            // Fita: int(line2down.size()) - jright.
          }
          checkFormatCondition(0 <= jright and jright < int(line3down.size()) and line3down[jright] == '|');
          // HI: readVisualFormatRec(v, i+4, jright, t.getRight()) llegeix correctament el subarbre dret.
          // Fita: en la crida recursiva, el nombre de línies pendents de processar del subarbre dret és menor que el del subarbre actual.
          readVisualFormatRec(v, i + 4, jright, t.getRight());
        }
      }
    }
  }
}

template <typename T>
void BinaryTree<T>::readVisualFormat(const vector<string> &v, BinaryTree<T> &t) {
  if (int(v.size()) == 0) {
    t = BinaryTree<T>();
  } else {
    readVisualFormatRec(v, 0, firstNonBlankPosInString(v[0]), t);
  }
}

template <typename T>
vector<string> BinaryTree<T>::generateVisualFormatRec(const BinaryTree<T> &t) {
  // Fita de la funció recursiva: nombre de nodes de t.
  vector<string> result;
  if (not t.isEmpty()) {
    string rootstring = value2string(t.getRoot());
    int rootrelativepos = (int(rootstring.size()) - 1) / 2;

    // HI: generateVisualFormatRec(t.getLeft()) genera correctament la representació visual del subarbre esquerre.
    // Fita: nombre de nodes de t.getLeft() < nombre de nodes de t.
    vector<string> leftresult = generateVisualFormatRec(t.getLeft());
    int leftrootpos = 0;
    if (int(leftresult.size()) > 0) {
      leftrootpos = obtainRootPositionInString(leftresult[0]);
    }

    // HI: generateVisualFormatRec(t.getRight()) genera correctament la representació visual del subarbre dret.
    // Fita: nombre de nodes de t.getRight() < nombre de nodes de t.
    vector<string> rightresult = generateVisualFormatRec(t.getRight());
    int rightrootpos = 0;
    if (int(rightresult.size()) > 0) {
      rightrootpos = obtainRootPositionInString(rightresult[0]);
    }

    if (int(leftresult.size()) == 0 and int(rightresult.size()) == 0) {
      result.push_back(rootstring);
    } else if (int(leftresult.size()) == 0) {
      int rootpos = rightrootpos - MINNUMHYPENSDESCENDANT - 1;
      if (rootpos - rootrelativepos < 0) {
        insertSpaceVectorString(-(rootpos - rootrelativepos), rightresult);
        rightrootpos += -(rootpos - rootrelativepos);
        rootpos = rootrelativepos;
      }
      result.push_back(string(rootpos - rootrelativepos, ' ') + rootstring);
      result.push_back(string(rootpos, ' ') + string(1, '|'));
      result.push_back(string(rootpos + 1, ' ') + string(rightrootpos - rootpos - 1, '-'));
      result.push_back(string(rightrootpos, ' ') + string(1, '|'));
      int i = 0;
      // Inv: result conté, després de les línies de la capçalera, les primeres i línies de rightresult en el mateix ordre.
      while (i < int(rightresult.size())) {
        result.push_back(rightresult[i]);
        ++i;
        // Fita: int(rightresult.size()) - i.
      }
    } else if (int(rightresult.size()) == 0) {
      int rootpos = leftrootpos + MINNUMHYPENSDESCENDANT + 1;
      if (rootpos - rootrelativepos < 0) {
        insertSpaceVectorString(-(rootpos - rootrelativepos), leftresult);
        leftrootpos += -(rootpos - rootrelativepos);
        rootpos = rootrelativepos;
      }
      result.push_back(string(rootpos - rootrelativepos, ' ') + rootstring);
      result.push_back(string(rootpos, ' ') + string(1, '|'));
      result.push_back(string(leftrootpos + 1, ' ') + string(max(0, rootpos - leftrootpos - 1), '-'));
      result.push_back(string(leftrootpos, ' ') + string(1, '|'));
      int i = 0;
      // Inv: result conté, després de les línies de la capçalera, les primeres i línies de leftresult en el mateix ordre.
      while (i < int(leftresult.size())) {
        result.push_back(leftresult[i]);
        ++i;
        // Fita: int(leftresult.size()) - i.
      }
    } else {
      int addspace = leftrootpos + 2 + 2 * MINNUMHYPENSDESCENDANT - rightrootpos;
      int i = 0;
      // Inv: addspace és prou gran per garantir la separació horitzontal correcta de totes les parelles de files ja examinades de leftresult i rightresult.
      while (i < int(leftresult.size()) and i < int(rightresult.size())) {
        addspace = max(addspace, int(leftresult[i].size()) - firstNonBlankPosInString(rightresult[i]) + MINSPACEBETWEENSUBTREES);
        ++i;
        // Fita: min(int(leftresult.size()), int(rightresult.size())) - i.
      }
      if ((rightrootpos + addspace - leftrootpos) % 2 == 1) {
        ++addspace;
      }
      if (addspace > 0) {
        insertSpaceVectorString(addspace, rightresult);
        rightrootpos += addspace;
      } else if (addspace < 0) {
        insertSpaceVectorString(-addspace, leftresult);
        leftrootpos += -addspace;
      }

      int rootpos = (leftrootpos + rightrootpos) / 2;
      if (rootpos - rootrelativepos < 0) {
        insertSpaceVectorString(-(rootpos - rootrelativepos), leftresult);
        insertSpaceVectorString(-(rootpos - rootrelativepos), rightresult);
        leftrootpos += -(rootpos - rootrelativepos);
        rightrootpos += -(rootpos - rootrelativepos);
        rootpos = rootrelativepos;
      }

      result.push_back(string(rootpos - rootrelativepos, ' ') + rootstring);
      result.push_back(string(rootpos, ' ') + string(1, '|'));
      result.push_back(string(leftrootpos + 1, ' ') + string(rootpos - leftrootpos - 1, '-') + string(1, ' ') + string(max(0, rightrootpos - rootpos - 1), '-'));
      result.push_back(string(leftrootpos, ' ') + string(1, '|') + string(rightrootpos - leftrootpos - 1, ' ') + string(1, '|'));

      i = 0;
      // Inv: result conté, després de la capçalera, la fusió correcta de les primeres i files de leftresult i rightresult.
      while (i < int(leftresult.size()) or i < int(rightresult.size())) {
        if (i < int(leftresult.size()) and i < int(rightresult.size())) {
          string &leftline = leftresult[i];
          string &rightline = rightresult[i];
          int leftsize = int(leftline.size());
          int rightsize = int(rightline.size());
          int size = max(leftsize, rightsize);
          string line(size, ' ');
          int j = 0;
          // Inv: per a tota posició k < j, line[k] ja conté el caràcter correcte resultant de fusionar leftline i rightline a la columna k.
          while (j < size) {
            if (j < leftsize and leftline[j] != ' ') {
              line[j] = leftline[j];
            } else if (j < rightsize and rightline[j] != ' ') {
              line[j] = rightline[j];
            }
            ++j;
            // Fita: size - j.
          }
          result.push_back(line);
        } else if (i < int(leftresult.size())) {
          result.push_back(leftresult[i]);
        } else {
          result.push_back(rightresult[i]);
        }
        ++i;
        // Fita: max(int(leftresult.size()), int(rightresult.size())) - i.
      }
    }
  }
  return result;
}

template <class T>
vector<string> BinaryTree<T>::generateVisualFormat(const BinaryTree<T> &t) {
  vector<string> v = generateVisualFormatRec(t);
  v.push_back(string());
  return v;
}

template <class T>
std::ostream &operator<<(std::ostream &os, const BinaryTree<T> &t) {
  int format = t.getOutputFormat();
  if (format == BinaryTree<T>::INLINEFORMAT) {
    BinaryTree<T>::writeStringTree(os, t);
  } else if (format == BinaryTree<T>::POSTORDERFORMAT) {
    BinaryTree<T>::writeBinaryTreePostOrder(os, t);
  } else {
    vector<string> result;
    if (format == BinaryTree<T>::LEFTVISUALFORMAT) {
      result = BinaryTree<T>::generateLeftVisualFormatRec(t);
    } else if (format == BinaryTree<T>::VISUALFORMAT) {
      result = BinaryTree<T>::generateVisualFormat(t);
    }
    int i = 0;
    // Inv: ja s'han escrit al flux, en ordre, les primeres i línies de result, cadascuna amb el salt de línia que li correspon.
    while (i < int(result.size())) {
      os << result[i];
      if (i < int(result.size()) - 1) {
        os << std::endl;
      }
      ++i;
      // Fita: int(result.size()) - i.
    }
  }
  return os;
}

template <class T>
std::istream &operator>>(std::istream &is, BinaryTree<T> &t) {
  int format = t.getInputFormat();
  if (format == BinaryTree<T>::INLINEFORMAT) {
    string s;
    is >> s;
    BinaryTree<T>::readStringTree(s, t);
  } else if (format == BinaryTree<T>::POSTORDERFORMAT) {
    BinaryTree<T>::readBinaryTreePostOrder(is, t);
  } else if (format == BinaryTree<T>::LEFTVISUALFORMAT) {
    BinaryTree<T>::readLeftVisualFormat(is, t);
  } else {
    vector<string> v;
    string line;
    // Inv: v conté, en el mateix ordre, totes les línies no buides llegides del flux abans de l'iteració actual.
    while (getline(is, line) and line != "") {
      v.push_back(line);
      // Fita: nombre de línies no buides que queden fins a la primera línia buida o EOF.
    }
    BinaryTree<T>::readVisualFormat(v, t);
  }
  return is;
}
 
template <typename T>
void BinaryTree<T>::minAtDepth(vector<T>& result) const {
}

#endif // BINARYTREE_HPP
