// Problem 1
bool BinaryTree::isFullRecursion(Node *root) {
    if (root == nullptr)
        return true;
    int mid = 1;
    if (root->left!=nullptr && root->right == nullptr)
        mid = 0;
    if (root->left==nullptr && root->right != nullptr)
        mid = 0;
    int left = isFullRecursion(root->left);
    int right = isFullRecursion(root->right);
    return mid && left && right;
}

bool BinaryTree::isFull()
{
    return isFullRecursion(root);
}

// Problem 2
int BinaryTree::countNodeRecursion(Node *root)
{
    if (root == nullptr)
        return 0;
    int count = 0;
    int left = countNodeRecursion(root->left);
    int right = countNodeRecursion(root->right);
    return left + right + 1;
}

bool BinaryTree::isCompleteRecursion(Node *root) {
    if (root == nullptr)
        return true;
    int height = getHeightRecursion(root);
    int numNode = countNodeRecursion(root);
    if (numNode == pow(2, height)-1)
        return true;
    return false;
}

bool BinaryTree::isComplete()
{
    return isCompleteRecursion(root);
}

// Problem 3
bool BinaryTree::isNearlyComplete()
{
    return isNearlyComplete2(root);
}

bool BinaryTree::isNearlyComplete2(Node *root) {
    if (root == NULL)
        return true;
    Queue<Node*> q;
    q.enQueue(root);
    bool leafFound = false;
    Node* temp;
    while(!q.isClear()) {
        q.deQueue(temp);
        if((leafFound == true) && (temp->left != NULL || temp->right != NULL))
            return false;
        if(temp->left == NULL && temp->right != NULL)
            return false;
        if(temp->left == NULL && temp->right ==NULL && leafFound == false)
            leafFound = true;
        if(temp->left)
            q.enQueue(temp->left);
        if(temp->right)
            q.enQueue(temp-> right);
    }
    return true;
}

//Problem 4
int BinaryTree::findLCARecursion(Node *root, int num1, int num2)
{
    if (root->data == num1 || root->data == num2)
        return root->data;
    if (root->data > num1 && root->data > num2)
        return findLCARecursion(root->left, num1, num2);
    if (root->data < num1 && root->data < num2)
        return findLCARecursion(root->right, num1, num2);
    return root->data;
}

int BinaryTree::findLCA(int num1, int num2)
{
    return findLCARecursion(root, num1, num2);
}