//19127421 - count leaf
int countLeaf(Node* p_root)
{
    if (!p_root)
        return 0;
    if (!p_root->p_left && !p_root->p_right)
        return 1;
    return countLeaf(p_root->p_left) + countLeaf(p_root->p_right);
}
//19127312 -count Less
int countLess(Node* root, int x) {
    if (root == nullptr) { return 0; }
    int left = countLess(root->p_left, x);
    int right = countLess(root->p_right, x);
    if (root->key < x) { // if(root->key > x chỉ gọi đệ quy cho bên trái)
        return 1 + left + right;
    }
    else {
        return left + right;
    }
}

int MaxValue(Node* root)
{
    if (!root)
        return 0;

    if (!root->p_left && !root->p_right)
        return root->key;
    else
    {
        int left = MaxValue(root->p_left);
        int right = MaxValue(root->p_right);
        if (left > right)
            return left;
        return right;
    }
}

int MinValue(Node* root)
{
    if (!root)
        return 0;

    if (!root->p_left && !root->p_right)
        return root->key;
    else
    {
        int left = MinValue(root->p_left);
        int right = MinValue(root->p_right);
        if (left < right)
            return left;
        return right;
    }
}

//19127652 - Check a given tree is a bst
bool IsBST(Node* root)
{
    if (root)
    {
        if (root->p_left)
            if (MaxValue(root->p_left) > root->key)
                return false;
        if (root->p_right)
            if (MinValue(root->p_right) < root->key)
                return false;
        return IsBST(root->p_left) && IsBST(root->p_right);
    }
    return true;
}

//19127039 - check full binary search tree
bool isFull(Node* root) {
    if (root == NULL)
        return true;
    if (root->p_left == NULL && root->p_right == NULL)
        return true;
    if (root->p_left && root->p_right)
        return isFull(root->p_left) && isFull(root->p_right);

    return false;
}
bool isFullBST(Node* root) {
    return IsBST(root) && isFull(root);
}