#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

// bst'yi (binary search tree) temsil eden sinifimiz.
class BinarySearchTree {
public:
    BinarySearchTree();  // Yapici metot
    ~BinarySearchTree(); // Yikici metot
    bool addItem(const int &item);  // Yeni eleman ekleme
    bool deleteItem(const int &item);  // Eleman silme
    void preOrderTraversal();  // Preorder dolasim
    void postOrderTraversal();  // Postorder dolasim
    void inOrderTraversal();  // Inorder dolasim
    int numberOfLeaves();  // Yaprak sayisini dondurur
    int getHeight();  // Agacin yuksekligini dondurur

private:
    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);

    Node *head;  // bst'nin ilk elemani
};

#endif

#include "BinarySearchTree.h"
#include <iostream>

// Constructor
BinarySearchTree::BinarySearchTree() {
    head = NULL;  // Baslangicta head'i NULL olarak ayarliyoruz
}

// Yeni bir eleman eklemek icin kullanilan metot
bool BinarySearchTree::addItem(const int &item) {
    return addNodeItem(item, head);
}

// bst'deki bir elemani silmek icin kullanilan metot
bool BinarySearchTree::deleteItem(const int &item) {
    return deleteNodeItem(item, head);
}

// bst'nin preOrder gezintisini gerceklestirir
void BinarySearchTree::preOrderTraversal() {
    preOrder(head);
}

// bst'nin postOrder gezintisini gerceklestirir
void BinarySearchTree::postOrderTraversal() {
    postOrder(head);
}

// bst'nin inOrder gezintisini gerceklestirir
void BinarySearchTree::inOrderTraversal() {
    inOrder(head);
}

// Agactaki yaprak sayisini dondurur
int BinarySearchTree::numberOfLeaves() {
    return countLeaves(head);
}

// Agacin yuksekligini hesaplar ve dondurur
int BinarySearchTree::getHeight() {
    return getHeight(head);
}

// Destructure
BinarySearchTree::~BinarySearchTree() {
    // Agaci temizleme islemi burada yapilabilir
}

// Yeni eleman ekleyen yardimci metot
bool BinarySearchTree::addNodeItem(const int &item, Node *&node) {
    if(node == NULL) {
        node = new Node();
        node->item = item;
        node->left = node->right = NULL;
        return true;
    }
    else if(item < node->item)
        return addNodeItem(item, node->left);
    else if(item > node->item)
        return addNodeItem(item, node->right);
    else
        return false;  // Dublicate elemanlar eklenmiyor
}

// Eleman silen yardimci metot
bool BinarySearchTree::deleteNodeItem(const int &item, Node *&node) {
    if(node == NULL)
        return false;  // Eleman bulunamadi
    if(item < node->item)
        return deleteNodeItem(item, node->left);
    else if(item > node->item)
        return deleteNodeItem(item, node->right);
    else {
        if(node->left == NULL && node->right == NULL) {
            delete node;
            node = NULL;
        }
        else if(node->left == NULL) {
            Node *temp = node;
            node = node->right;
            delete temp;
        }
        else if(node->right == NULL) {
            Node *temp = node;
            node = node->left;
            delete temp;
        }
        else
            exchange(node, node->right);
        return true;
    }
}

// Node degistirme yardimci metot
void BinarySearchTree::exchange(Node *&dNode, Node *&fNode) {
    if(fNode->left == NULL) {
        dNode->item = fNode->item;
        Node *temp = fNode;
        fNode = fNode->right;
        delete temp;
    }
    else
        exchange(dNode, fNode->left);
}

// Preorder dolasim
void BinarySearchTree::preOrder(Node *&node) {
    if(node != NULL) {
        std::cout << node->item << std::endl;
        preOrder(node->left);
        preOrder(node->right);
    }
}

// Postorder dolasim
void BinarySearchTree::postOrder(Node *&node) {
    if(node != NULL) {
        postOrder(node->left);
        postOrder(node->right);
        std::cout << node->item << std::endl;
    }
}

// Inorder dolasim
void BinarySearchTree::inOrder(Node *&node) {
    if(node != NULL) {
        inOrder(node->left);
        std::cout << node->item << std::endl;
        inOrder(node->right);
    }
}

// Yaprak sayisini sayan metot
int BinarySearchTree::countLeaves(Node *&node) {
    if(node == NULL)
        return 0;
    else if(node->left == NULL && node->right == NULL)
        return 1;
    else
        return countLeaves(node->left) + countLeaves(node->right);
}

// Agacin yuksekligini hesaplayan metot
int BinarySearchTree::getHeight(Node *&node) {
    if(node == NULL)
        return 0;
    else {
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        return (leftHeight > rightHeight) ? leftHeight + 1 : rightHeight + 1;
    }
}