#ifndef BINARYTREE_HPP
#define BINARYTREE_HPP

#include <cstdlib>
#include <algorithm>
#include <queue>
#include <memory>

template<class T>
class Node {

   private:
      std::shared_ptr< Node<T> > rChild;
      std::shared_ptr< Node<T> > lChild;
      T val;

   public:
      Node() { rChild = nullptr; lChild = nullptr; };
      Node( const T v ) { val = v; rChild = nullptr; lChild = nullptr; };
      T getVal() { return val; };
      std::shared_ptr< Node<T> > getLeft() { return lChild; };
      std::shared_ptr< Node<T> > getRight() { return rChild; };
      void setLeft( std::shared_ptr< Node<T> > n) { lChild = n; };
      void setRight( std::shared_ptr< Node<T> > n) { rChild = n; };
};

template<class T>
class Tree {

   private:
      std::shared_ptr< Node<T> > root;

   public:
      Tree() { root = nullptr; };
      Tree( std::shared_ptr< Node<T> > node ) { root = node; };
      void insert( const T );
      void remove( const T );
      bool isIn( const T ) const;
      size_t height() const;
      void inorder() const;
      void postorder() const;
      void preorder() const;
      bool isBalanced() const;
      std::shared_ptr< Node<T> > getPointer( T ) const;
      std::shared_ptr< Node<T> > getRoot() const { return root; };
      std::shared_ptr< Node<T> > getLeft() const { return root->getLeft(); };
      std::shared_ptr< Node<T> > getRight() const { return root->getRight(); };
      void print();
      std::shared_ptr< Node<T> > kthNode( int& ) const;
};

template<class T>
void Tree<T>::insert( const T val ) {

   std::shared_ptr< Node<T> > newNode( new Node<T>( val ) );

   if (root == nullptr) {
      root = newNode;
   }
   else {

      if ( val > root->getVal() ) {
         if (root->getRight() == nullptr) {
            root->setRight( newNode );
         }
         else {
            Tree<T>( root->getRight() ).insert(val);
         }
      }
      else if ( val < root->getVal() ) {
         if (root->getLeft() == nullptr) {
            root->setLeft( newNode );
         }
         else {
            Tree<T>( root->getLeft() ).insert(val);
         }
      }
   }
}

template<class T>
bool Tree<T>::isIn( const T v ) const {
   if ( root == nullptr ) {
      return false;
   }
   else{
      if ( v > root->getVal() ) {
         return Tree<T>( root->getRight() ).isIn(v);
      }
      else if ( v < root->getVal() ) {
         return Tree<T>( root->getLeft() ).isIn(v);
      }
      else {
         return true;
      }
   }
}

template<class T>
size_t Tree<T>::height() const {

   if (root == nullptr){
      return 0;
   }
   else {
      return 1 + std::max( Tree<T>(root->getLeft()).height() , Tree<T>(root->getRight()).height() );
   }
}

template<class T>
void Tree<T>::preorder() const {

   if ( root == nullptr ) {
      return;
   }

   std::cout << root->getVal() << std::endl;  
   Tree<T>( root->getLeft() ).preorder();     
   Tree<T>( root->getRight() ).preorder();    
}

template<class T>
void Tree<T>::inorder() const {

   if ( root == nullptr ) {
      return;
   }

   Tree<T>( root->getLeft() ).inorder();      
   std::cout << root->getVal() << std::endl;  
   Tree<T>( root->getRight() ).inorder();     
}

template<class T>
void Tree<T>::postorder() const {

   if ( root == nullptr ) {
      return;
   }

   Tree<T>( root->getLeft() ).postorder();    
   Tree<T>( root->getRight() ).postorder();   
   std::cout << root->getVal() << std::endl;  
}

template<class T>
bool Tree<T>::isBalanced() const {

   if ( root == nullptr ) {
      return true;
   }
   else {
      Tree<T> left = Tree<T>( root->getLeft() );
      Tree<T> right = Tree<T>( root->getRight() );

      return left.isBalanced() && right.isBalanced() && ( std::abs( (int) (left.height() - right.height()) ) <= 1);
   }
}

template<class T>
std::shared_ptr< Node<T> > Tree<T>::getPointer( T val ) const {

   std::shared_ptr< Node<T> > res = nullptr;

   if ( root != nullptr ) {

      if ( res != nullptr ) {
         return res;
      }
      if (val == root->getVal() ){
         return root;
      }

      if( root->getLeft() != nullptr ) {
         res = Tree<T>( root->getLeft() ).getPointer( val );
      }

      if ( root->getRight() != nullptr ) {
         res = Tree<T>( root->getRight() ).getPointer( val );
      }
   }

   return res;
}

template<class T>
void Tree<T>::print() {

   std::queue< std::shared_ptr< Node<T> > > row;
   row.push(root);

   while ( !row.empty() ) {

      std::queue< std::shared_ptr< Node<T> > > next;

      while ( !row.empty() ) {

         std::shared_ptr< Node<T> > n = row.front();
         row.pop();

         if ( n != nullptr ) {
            std::cout << n->getVal() << "  ";
         }

         if ( n->getLeft() != nullptr ) {
            next.push( n->getLeft() );
         }
         if ( n->getRight() != nullptr ) {
            next.push( n->getRight() );
         }
      }

      std::cout << std::endl;

      row = next;
   }
}

template<class T>
std::shared_ptr< Node<T> > Tree<T>::kthNode( int &k ) const {

   std::shared_ptr< Node<T> > res = nullptr;

   if ( root != nullptr ) {

      if( root->getLeft() != nullptr ) {
         res = Tree<T>( root->getLeft() ).kthNode( k );
      }

      if ( res == nullptr ) {
         if ( k == 0 ) {
            res = root;
         }

         k--;
      }

      if ( res == nullptr and ( root->getRight() != nullptr ) ) {
         res = Tree<T>( root->getRight() ).kthNode( k );
      }
   }

   return res;
}

template<class T>
bool equal( const Tree<T> t1, const Tree<T> t2 ) {

   if ( t1.getRoot() != nullptr and t2.getRoot() == nullptr ) {
      return false;
   }

   else if ( t1.getRoot() == nullptr and t2.getRoot() != nullptr ) {
      return false;
   }

   else if ( t1.getRoot() == nullptr and t2.getRoot() == nullptr ) {
      return true;
   }

   else {
      return ( t1.getRoot()->getVal() == t2.getRoot()->getVal() )
         and equal( Tree<T>( t1.getLeft()  ), Tree<T>( t2.getLeft() )  )
         and equal( Tree<T>( t1.getRight() ), Tree<T>( t2.getRight() ) );
   }
}

#endif

#ifndef BINARYTREE_HPP
#define BINARYTREE_HPP

#include <cstdlib>
#include <algorithm>
#include <queue>
#include <memory>

template<class T>
class Node {

   private:
      std::shared_ptr< Node<T> > rChild;
      std::shared_ptr< Node<T> > lChild;
      T val;

   public:
      Node() { rChild = nullptr; lChild = nullptr; };
      Node( const T v ) { val = v; rChild = nullptr; lChild = nullptr; };
      T getVal() { return val; };
      std::shared_ptr< Node<T> > getLeft() { return lChild; };
      std::shared_ptr< Node<T> > getRight() { return rChild; };
      void setLeft( std::shared_ptr< Node<T> > n) { lChild = n; };
      void setRight( std::shared_ptr< Node<T> > n) { rChild = n; };
};

template<class T>
class Tree {

   private:
      std::shared_ptr< Node<T> > root;

   public:
      Tree() { root = nullptr; };
      Tree( std::shared_ptr< Node<T> > node ) { root = node; };
      void insert( const T );
      void remove( const T );
      bool isIn( const T ) const;
      size_t height() const;
      void inorder() const;
      void postorder() const;
      void preorder() const;
      bool isBalanced() const;
      std::shared_ptr< Node<T> > getPointer( T ) const;
      std::shared_ptr< Node<T> > getRoot() const { return root; };
      std::shared_ptr< Node<T> > getLeft() const { return root->getLeft(); };
      std::shared_ptr< Node<T> > getRight() const { return root->getRight(); };
      void print();
      std::shared_ptr< Node<T> > kthNode( int& ) const;
};

template<class T>
void Tree<T>::insert( const T val ) {

   std::shared_ptr< Node<T> > newNode( new Node<T>( val ) );

   if (root == nullptr) {
      root = newNode;
   }
   else {

      if ( val > root->getVal() ) {
         if (root->getRight() == nullptr) {
            root->setRight( newNode );
         }
         else {
            Tree<T>( root->getRight() ).insert(val);
         }
      }
      else if ( val < root->getVal() ) {
         if (root->getLeft() == nullptr) {
            root->setLeft( newNode );
         }
         else {
            Tree<T>( root->getLeft() ).insert(val);
         }
      }
   }
}

template<class T>
bool Tree<T>::isIn( const T v ) const {
   if ( root == nullptr ) {
      return false;
   }
   else{
      if ( v > root->getVal() ) {
         return Tree<T>( root->getRight() ).isIn(v);
      }
      else if ( v < root->getVal() ) {
         return Tree<T>( root->getLeft() ).isIn(v);
      }
      else {
         return true;
      }
   }
}

template<class T>
size_t Tree<T>::height() const {

   if (root == nullptr){
      return 0;
   }
   else {
      return 1 + std::max( Tree<T>(root->getLeft()).height() , Tree<T>(root->getRight()).height() );
   }
}

template<class T>
void Tree<T>::preorder() const {

   if ( root == nullptr ) {
      return;
   }

   std::cout << root->getVal() << std::endl;  //Vist node.
   Tree<T>( root->getLeft() ).preorder();     //Deal with left.
   Tree<T>( root->getRight() ).preorder();    //Deal with right.
}

template<class T>
void Tree<T>::inorder() const {

   if ( root == nullptr ) {
      return;
   }

   Tree<T>( root->getLeft() ).inorder();      //Deal with left.
   std::cout << root->getVal() << std::endl;  //Vist node.
   Tree<T>( root->getRight() ).inorder();     //Deal with right.
}

template<class T>
void Tree<T>::postorder() const {

   if ( root == nullptr ) {
      return;
   }

   Tree<T>( root->getLeft() ).postorder();    //Deal with left.
   Tree<T>( root->getRight() ).postorder();   //Deal with right.
   std::cout << root->getVal() << std::endl;  //Vist node.
}

template<class T>
bool Tree<T>::isBalanced() const {

   if ( root == nullptr ) {
      return true;
   }
   else {
      Tree<T> left = Tree<T>( root->getLeft() );
      Tree<T> right = Tree<T>( root->getRight() );

      return left.isBalanced() && right.isBalanced() && ( std::abs( (int) (left.height() - right.height()) ) <= 1);
   }
}


template<class T>
std::shared_ptr< Node<T> > Tree<T>::getPointer( T val ) const {

   std::shared_ptr< Node<T> > res = nullptr;

   if ( root != nullptr ) {

      if ( res != nullptr ) {
         return res;
      }
      if (val == root->getVal() ){
         return root;
      }

      if( root->getLeft() != nullptr ) {
         res = Tree<T>( root->getLeft() ).getPointer( val );
      }

      if ( root->getRight() != nullptr ) {
         res = Tree<T>( root->getRight() ).getPointer( val );
      }
   }

   return res;
}

template<class T>
void Tree<T>::print() {

   std::queue< std::shared_ptr< Node<T> > > row;
   row.push(root);

   while ( !row.empty() ) {

      std::queue< std::shared_ptr< Node<T> > > next;

      while ( !row.empty() ) {

         std::shared_ptr< Node<T> > n = row.front();
         row.pop();

         if ( n != nullptr ) {
            std::cout << n->getVal() << "  ";
         }

         if ( n->getLeft() != nullptr ) {
            next.push( n->getLeft() );
         }
         if ( n->getRight() != nullptr ) {
            next.push( n->getRight() );
         }
      }

      std::cout << std::endl;

      row = next;
   }
}

template<class T>
std::shared_ptr< Node<T> > Tree<T>::kthNode( int &k ) const {
   /*returns the kth node inorder.*/

   std::shared_ptr< Node<T> > res = nullptr;

   if ( root != nullptr ) {

      if( root->getLeft() != nullptr ) {
         res = Tree<T>( root->getLeft() ).kthNode( k );
      }

      if ( res == nullptr ) {
         if ( k == 0 ) {
            res = root;
         }

         k--;
      }

      if ( res == nullptr and ( root->getRight() != nullptr ) ) {
         res = Tree<T>( root->getRight() ).kthNode( k );
      }
   }

   return res;
}

template<class T>
bool equal( const Tree<T> t1, const Tree<T> t2 ) {
   /*Determines whether the two trees are the same by structure and values.*/

   if ( t1.getRoot() != nullptr and t2.getRoot() == nullptr ) {
      return false;
   }

   else if ( t1.getRoot() == nullptr and t2.getRoot() != nullptr ) {
      return false;
   }

   else if ( t1.getRoot() == nullptr and t2.getRoot() == nullptr ) {
      return true;
   }

   else {
      return ( t1.getRoot()->getVal() == t2.getRoot()->getVal() )
         and equal( Tree<T>( t1.getLeft()  ), Tree<T>( t2.getLeft() )  )
         and equal( Tree<T>( t1.getRight() ), Tree<T>( t2.getRight() ) );
   }
}

#endif

