#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include <cstdlib>
#include <iostream>
using namespace std;
//bst yi binary search tree derken kullanicam
//Yeni bir bst olusturuyoruz
class BinarySearchTree{
public  :
        //Constructor ve diger methodlarin tanimlanmasi 
        BinarySearchTree();
        bool addItem(const int &item);
        bool deleteItem(const int &item);
        void preOrderTraversal();
        void postOrderTraversal();
        void inOrderTraversal();
        int numberOfLeaves();
        int getHeight();
private :
        //Node adinda yeni bir yapi(struct) olusturuyoruz
        struct Node{
            int item;
            Node *right;
            Node *left;
        };
        bool addNodeItem(const int &item,Node *&node);
        bool deleteNodeItem(const int &item,Node *&node);
        void exchange(Node *&dNode,Node *&fNode);
        void preOrder(Node *&node);
        void postOrder(Node *&node);
        void inOrder(Node *&node);
        int countLeaves(Node *&node);
        int getHeight(Node *&node);
        //bst nin ilk elemani
        Node *head;
};
#endif

#include "BinarySearchTree.h"
//Constructor 
BinarySearchTree::BinarySearchTree(){
   head = NULL;
}
//yeni bir eleman eklemek icin kullacagimiz method
bool BinarySearchTree::addItem(const int &item){
     return addNodeItem(item,head);
}
//bst tedeki bir elamani silmek icin kulacagimiz method
bool BinarySearchTree::deleteItem(const int &item){
     return deleteNodeItem(item,head);
}
//bst nin preOrder traversalini dönderir
void BinarySearchTree::preOrderTraversal(){
     preOrder(head);
}
//bst nin postOrder traversalini dönderir
void BinarySearchTree::postOrderTraversal(){
     postOrder(head);
}
//bst nin inOrder traversalini dönderir
void BinarySearchTree::inOrderTraversal(){
     inOrder(head);
}
//agactaki yaprak sayisini donderir
int BinarySearchTree::numberOfLeaves(){
     return countLeaves(head);
}
int BinarySearchTree::getHeight(){
     return getHeight(head);
}
bool BinarySearchTree::addNodeItem(const int &item,Node *&node){
     //Eger node nullsa yeni bir node olusturup bunu null olan
     //node ile degistiriyoruz
     if(node==NULL){
         Node *newNode = new Node();
         newNode->item = item;
         node = newNode;
         return true;
     }
     //eger gelen item node daki itemden küçükse bunu
     //agacin sol elemanina yolluyoruz büyüksede agacin 
     //sag elemanina gonderiyoruz
     else if(item<node->item)
         return addNodeItem(item,node->left);
     else
         return addNodeItem(item,node->right);
}
bool BinarySearchTree:: deleteNodeItem(const int &item,Node *&node){
     //Eger node Null sa bu demek oluyor ki agactaki uygun eleman
     //lari gezmis ama istedigimiz nodu bulamamisizdir
     if(node == NULL)
         return false;
     //eger gelen item node daki itemden küçükse bunu
     //agacin sol elemanina yolluyoruz büyüksede agacin 
     //sag elemanina gonderiyoruz
     else if(item < node->item)
         return deleteNodeItem(item,node->left);
     else if(item > node->item)
         return deleteNodeItem(item,node->right);
     //bu durum nodu buldugumuz durum yani itemlerin esit olmasi
     else{
         //eger sag ve sol yaprak bossa direk siliyoruz cunku
         //bizi zora sokabilecek yaprak yok
         if(node->right==NULL&&node->left==NULL){
              node = NULL;
              delete node;
         }
         //eger sag ve ya soldan birisi doluysa oradaki sag elaman
         //ile bizim nodumuza esitleyerek kurtulmus oluyoruz
         else if(node->left==NULL)
              node = node->right;
         else if(node->right==NULL)
              node = node->left;
         //eger her ikiside doluysa exchange methodu bizim node ile
         //nodun sagindaki node a gidiyoruz.Burda sebep bizim node dan
         //buyuk olan ilk eleman sagdaki ilk node olmasi
         else
              exchange(node,node->right);
         return true;
     }
}
void BinarySearchTree:: exchange(Node *&dNode,Node *&fNode){
     //burada bize verilen sag nodun null olup olmadigina bakiyoruz
     //eger null deilse sol node ala ala en son sol nodu bulana kadar
     //asagi iniyoruz. Bunun sebebi en solda bulacagimiz sol nodu
     //tree nin dengesini bozmayacaktir. Cunku en son buldugumuz sol node
     //dnode dan asagida bulunan diger butun nodelardan kucuk olmasidir
     //en sonunda sagdaki elemanla degistirme nedenimizse agacin sag 
     //tarafinin korunmasini saglamak istedigimizdir.
     if(fNode->left == NULL){
         dNode->item = fNode->item;
         fNode = fNode->right;
     }
     else
         exchange(dNode,fNode->left);         
}
void BinarySearchTree:: preOrder(Node *&node){
     //burada preOrderi cagiriyoruz bu ilk once
     //kendi nodumuzu sonra left ve right nodu cagirmak demektir
     //preorderla agacimizi yeni bastan olusturabiliriz.
     if(node != NULL){
         cout<<node->item<<endl;
         preOrder(node->left);
         preOrder(node->right);
     }
}
void BinarySearchTree:: postOrder(Node *&node){
     //burada postOrderi cagiriyoruz bu ilk once
     //left ve right nodu sonra kendi nodumuzu cagirmak demektir
     //preorderla agacimizi yeni bastan olusturabiliriz.
     if(node != NULL){
         postOrder(node->left);
         postOrder(node->right);
         cout<<node->item<<endl;
     }
}
void BinarySearchTree:: inOrder(Node *&node){
     //burada inOrderi cagiriyoruz bu ilk once left yapragi
     //daha sonra nodun kendisini en sondada nodun sag elemanini
     //cagirmak demektir 
     //inorderla agacimizin sirali bir sekilde bastirilmasini saglariz.
     if(node != NULL){
         inOrder(node->left);
         cout<<node->item<<endl;
         inOrder(node->right);
     }
}
int BinarySearchTree:: countLeaves(Node *&node){
    //eger nodu nullsa 0 donder sayilacak yaprak yok demektir
    //degilse sag ve sol elamanlarda kac tane yaprak olduguna bak
    //onlari toplayip sonucu donmesi.
    if(node==NULL)
        return 0;
    else
        return countLeaves(node->left)+countLeaves(node->right)+1;
}
int BinarySearchTree:: getHeight(Node *&node){
    //eger node null sa boyu sifira esit demektir dolayisiyla
    //0 donuyoruz
    int right,left;
    if(node==NULL)
        return 0;
    //eger null degilse nodu un boyu sol ve sag cocugundan hangisinin
    //boyu daha uzunsa onun bir fazlasina esittir.
    else if((left=getHeight(node->left)+1)>(right=getHeight(node->right)+1))
        return left;
    else
        return right;
}

//**********************************************
// List.h
//**********************************************
#ifndef LIST_H
#define LIST_H
#include
#include
using namespace std;
class List{
public :
       List();//Constructor
       ~List();//Destructor
       void addItem(int item);//add integer item
       void deleteItem(int loc);//delete item
private:
       int *ptr,size;//pointer and its size
};
#endif

#include "List.h"
List::List(){
     size = 0;//We inialize size to 0
     //since initial size is 0
}
//addItem method which adds an item to
//the end of the list just like arrayList
void List::addItem(int item){
     //if size is 0 create an array
     if(size==0){
         ptr= new int[++size];
         ptr[size-1] = item;
     }
     //if size is not zero
     else{
         //we inialize a pointer which have size
         //of size+1 since we want to add one more
         //item to the end of the list
         int *newPtr;
         newPtr = new int [size+1];
         //we put the elements into new array
         for(int i=0;i<size;i++)
             newPtr[i] = ptr[i];
         //we lastly insert the item to the end of
         //the list
         newPtr[size++] = item;
         //we delete the ptr pointer's elements
         //since they use memory
         delete [] ptr;
         //Lastly we use address of newPtr for ptr
         ptr = newPtr;
     }
}
//deleteItem method which deletes an item by given
//location which specify array position.
void List::deleteItem(int loc){
     //we inialize a pointer which have size
     //of size-1 since we want to delete one
     //item which is on location loc
     int *newPtr;
     newPtr = new int [size--];
     //we put the elements into newPtr until
     //we come accross to the given location
     for(int i=0;i<loc-1;i++)
         newPtr[i] = ptr[i];
     //after that we do not put the ptr[loc]
     //so that it will be deleted
     for(int i=loc;i<size;i++)
         newPtr[i] = ptr[i+1];
     //we delete the ptr pointers' elements
     //since they use memory
     delete [] ptr;
     //Lastly we use address of newPtr for ptr
     ptr = newPtr;
}
//Destructor
List::~List(){
     //we delete the ptr pointers' elements
     //since they use memory
     delete [] ptr;     
}