#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include <string>

using namespace std;

class Node
{
private:
   string data;
   Node* left;
   Node* right;
friend class BinaryTree;
};

/*
   Drzewo binarne, w którym każdy węzeł ma dwoje dzieci.
*/
class BinaryTree
{
public:
   /**
      Konstruuje puste drzewo.
   */
   BinaryTree();

   /**
      Konstruuje drzewo z jednym węzłem i bez dzieci.
      @param root_data dane w korzeniu
   */
   BinaryTree(string root_data);

   /**
      Konstruuje drzewo binarne.
      @param root_data dane w korzeniu
      @param left lewe poddrzewo
      @param right prawe poddrzewo
   */
   BinaryTree(string root_data, BinaryTree left, BinaryTree right);

   /**
      Zwraca wysokość drzewa.
      @return wysokość
   */
   int height() const;

   /**
      Sprawdza, czy drzewo jest puste.
      @return wartość true, jeśli drzewo jest puste
   */
   bool empty() const;

   /**
      Pobiera dane znajdujące się w korzeniu drzewa.
      @return dane z korzenia
   */
   string data() const;

   /**
      Pobiera lewe poddrzewo tego drzewa.
      @return lewe dziecko korzenia
   */
   BinaryTree left() const;

   /**
      Pobiera prawe poddrzewo tego drzewa.
      @return prawe dziecko korzenia
   */
   BinaryTree right() const;

private:
   /**
      Zwraca wysokość poddrzewa, którego korzeniem jest podany węzeł.
      @param n węzeł lub wskaźnik nullptr
      @return wysokość poddrzewa albo liczba 0, jeśli wskaźnik n ma wartość nullptr
   */
   int height(const Node* n) const;

   Node* root;
};

#endif

