#include <iostream>
#include <string>
using namespace std;

typedef string ItemType;

struct WordNode {
ItemType m_data;
WordNode *m_left;
WordNode *m_right;
// You may add additional data members and member functions in WordNode
int m_count; // to store the count of the word

WordNode(ItemType data)
{
m_data = data;
m_left = m_right = nullptr;
m_count = 1;//when a node is created , it means its appearing atleast once
}

WordNode(const WordNode &n)
{
m_data = n.m_data;
m_count = n.m_count;
if(n.m_left != nullptr)
m_left = new WordNode(*n.m_left);
else
m_left = nullptr;
if(n.m_right != nullptr)
m_right = new WordNode(*n.m_right);
else
m_right = nullptr;
}

int distinctWords()
{
int count = 1;
if(m_left != nullptr)
count += m_left->distinctWords();
if(m_right != nullptr)
count += m_right->distinctWords();
return count;
}

int totalWords()
{
int count = m_count;
if(m_left != nullptr)
count += m_left->totalWords();
if(m_right != nullptr)
count += m_right->totalWords();
return count;
}

friend ostream& operator << (ostream &out, const WordNode &n);

};

class WordTree {

private:
WordNode *root;
void deleteTree(WordNode *w); //recursively delete tree nodes in post order traversal
public:

// default constructor
WordTree() : root(nullptr) { };

// copy constructor
WordTree(const WordTree& rhs);

// assignment operator
const WordTree& operator=(const WordTree& rhs);

// Inserts val at the front of the list
void add(ItemType v);

// Returns the number of distince words / nodes
int distinctWords() const;

// Returns the total number of words inserted, including duplicate
// values
int totalWords() const;

// Prints the LinkedList
friend ostream& operator<<(ostream &out, const WordTree& rhs);

// Destroys all the dynamically allocated memory
// in the tree.
~WordTree();
};

WordTree::WordTree(const WordTree& rhs)
{
*this = rhs;
}

// assignment operator
const WordTree& WordTree::operator=(const WordTree& rhs)
{
if(rhs.root == nullptr)
root = nullptr;
else
root = new WordNode(*rhs.root);
return *this;
}

// Inserts val at the front of the list
void WordTree::add(ItemType v)
{

if(root == nullptr)
root = new WordNode(v);
else
{
WordNode *curr = root;
while(curr != nullptr)
{
if(curr->m_data == v) //already word in tree, increase count
{
curr->m_count++;
return;
}
else if(v < curr->m_data)
{
if(curr->m_left == nullptr)
{
curr ->m_left = new WordNode(v);
return;
}
else
curr = curr->m_left;
}
else
{

if(curr->m_right == nullptr)
{
curr ->m_right = new WordNode(v);
return;
}
else
curr = curr->m_right;
}
}
}
}
// Returns the number of distince words / nodes
int WordTree::distinctWords() const
{
if(root == nullptr)
return 0;
else
return root->distinctWords();
}

// Returns the total number of words inserted, including duplicate
// values
int WordTree::totalWords() const
{
if(root == nullptr)
return 0;
else
return root->totalWords();

}

// Prints the LinkedList
ostream& operator<<(ostream &out, const WordTree& rhs)
{
if(rhs.root != nullptr)
out << *rhs.root;
return out;

}

// Destroys all the dynamically allocated memory
// in the tree.
WordTree::~WordTree()
{
deleteTree(root);
}

void WordTree::deleteTree(WordNode *w)
{
if(w == nullptr) return;
deleteTree(w->m_left);
deleteTree(w->m_right);
delete w;
}

ostream& operator << (ostream &out, const WordNode &n)
{
if(n.m_left != nullptr)
out << *n.m_left;
out << n.m_data << "[" << n.m_count << "]" << endl;

if(n.m_right != nullptr)
out << *n.m_right;

return out;
}