#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;
}