BinaryTree

#ifndef __BINARYTREE_H__
#define __BINARYTREE_H__

#include <queue>
#include <iostream>
#include <math.h>

template <typename T>
class BinaryTreeNode {
private:
    T data;

    BinaryTreeNode<T> *leftChild;
    BinaryTreeNode<T> *rightChild;

public:
    int lvl;
    BinaryTreeNode<T> *tati;
    BinaryTreeNode<T> *T2;
    BinaryTreeNode(T data) {
        // TODO 1
        lvl = 0;
        this->data = data;
        tati = NULL;
        T2 = NULL;
        leftChild = NULL;
        rightChild = NULL;
    }

    ~BinaryTreeNode() {
        // TODO 2
    }

    void setData(T data) {
        // TODO 3
        this->data = data;
    }

    T getData() {
        // TODO 4
        return data;
    }

    void setLeftChild(T data) {
        // TODO 5
        leftChild = new BinaryTreeNode<T>(data);
        leftChild->data = data;
    }

    BinaryTreeNode<T>* getLeftChild() {
        // TODO 6
        return leftChild;
    }

    void setRightChild(T data) {
        // TODO 7
        rightChild = new BinaryTreeNode<T>(data);
    }

    BinaryTreeNode<T>* getRightChild() {
        // TODO 8
        return rightChild;
    }
};

template <typename T>
class BinaryTree {
private:
    int size, H;
    BinaryTreeNode<T> *root;

public:
    BinaryTree() {
        // TODO 9
        size = 0;
        root = NULL;
    }

    ~BinaryTree() {
        // TODO 10
        BinaryTreeNode<T>* tmp = root;
        std::queue<BinaryTreeNode<T>*> Q;
        Q.push(root);
        while(!Q.empty()) {
            tmp = Q.front();
            Q.pop();
            if (tmp->getLeftChild() != NULL) {
                Q.push(tmp->getLeftChild());
            }
            if (tmp->getRightChild() != NULL) {
                Q.push(tmp->getRightChild());
            }
            delete tmp;
        }

    }

    BinaryTreeNode<T>* getRoot() {
        // TODO: Si asta trebuie facut
        return root;
    }

    int getSize() {
        // Faceti-l
        return size;
    }

    void insert(T data) {
        // TODO 11: Insert node at the first empty position
        if (size == 0) {
            root = new BinaryTreeNode<T>(data);
            root->setData(data);
            ++size;
            return;
        }
        BinaryTreeNode<T> *tmp = root;
        std::queue<BinaryTreeNode<T>*> Q;
        Q.push(root);
        ++size;
        while(!Q.empty()) {
            tmp = Q.front();
            Q.pop();
            if (tmp->getLeftChild() == NULL) {
                tmp->setLeftChild(data);
                tmp->getLeftChild()->tati = tmp;
                return;
            }
            if (tmp->getRightChild() == NULL) {
                tmp->setRightChild(data);
                tmp->getRightChild()->tati = tmp;
                return;
            }
            Q.push(tmp->getLeftChild());
            Q.push(tmp->getRightChild());
        }
    }

    std::vector<T> printTraversal(BinaryTreeNode<T>* node) {
        // TODO 12
        // static startNode = node;
        // static std::vector<T> ans;
        // if (node->getLeftChild() != NULL) {
        //     printTraversal(node->getLeftChild());
        // }
        // ans.push_back(node);
        // if (node->getRightChild() != NULL) {
        //     printTraversal(node->getRightChild());
        // }
        // if (node == startNode) {
        //     return ans;
        // }
        BinaryTreeNode<T>* tmp = root;
        std::queue<BinaryTreeNode<T>*> Q;
        Q.push(root);
        while(!Q.empty()) {
            tmp = Q.front();
            std::cout << tmp->getData() << std::endl;
            Q.pop();
            if (tmp->getLeftChild() != NULL) {
                Q.push(tmp->getLeftChild());
            }
            if (tmp->getRightChild() != NULL) {
                Q.push(tmp->getRightChild());
            }
        }
    }
    int height() {
        int height = 1;
        while ((1 << height) - 1 <= size) {
            ++height;
        }
        --height;
        return height;
    }
    void getBuckets(BinaryTreeNode<T>* node, BinaryTreeNode<T>* tata, int level) {
        node->T2 = tata;
        node->lvl = level;
        if (level % H == 0) {
            tata = node;
        }
        if (node->getLeftChild() != NULL) {
            getBuckets(node->getLeftChild(), tata, level + 1);
        }
        if (node->getRightChild() != NULL) {
            getBuckets(node->getRightChild(), tata, level + 1);
        }

    }
    void lca(BinaryTreeNode<T>* x, BinaryTreeNode<T>* y) {
        H = height();
        H = sqrt(H);
        getBuckets(root, NULL, 0);
        while (x->T2 != y->T2) {
            if (x->lvl < y->lvl) {
                y = y->T2;
            } else {
                x = x->T2;
            }
        }
        while (x != y) {
            if (x->lvl < y->lvl) {
                y = y->tati;
            } else {
                x = x->tati;
            }
        }
        std::cout << x->getData();
    }
};

#endif // __BINARYTREE_H__