Untitled

#include <iostream>

using namespace std;
struct node {
    int value;
    node* left;
    node* right;
};
 
bool isMinHeapUtil(node* T) {
    if (T == nullptr) return true;
    if (T->left == nullptr && T->right == nullptr) return true;
 
    if (T->left == nullptr) return (T->value <= T->right->value) && isMinHeapUtil(T->right);
    if (T->right == nullptr) return (T->value <= T->left->value) && isMinHeapUtil(T->left);
 
    return (T->value <= T->left->value) && (T->value <= T->right->value) && isMinHeapUtil(T->left) && isMinHeapUtil(T->right);
}
 
bool isMinHeap(node* T) {
    return isMinHeapUtil(T);
}
 
//1a
 
 
 
int biggestMinHeap(node* T) {
    if (T == nullptr) return 0;
 
    int left = biggestMinHeap(T->left);
    int right = biggestMinHeap(T->right);
 
    if (T->left != nullptr && T->value > T->left->value) return max(left, right);
    if (T->right != nullptr && T->value > T->right->value) return max(left, right);
 
    return 1 + left + right;
}
//1b
 
 
bool biggestMinBinaryHeap(node* T, int &maxSize) {
    if (T == nullptr) return true;
 
    bool leftIsMinHeap = biggestMinBinaryHeap(T->left, maxSize);
    bool rightIsMinHeap = biggestMinBinaryHeap(T->right, maxSize);
 
    if (!leftIsMinHeap || !rightIsMinHeap) return false;
 
    int leftSize = 0;
    int rightSize = 0;
    if (T->left != nullptr) {
        if (T->value > T->left->value) return false;
        leftSize = 1 + biggestMinBinaryHeap(T->left->left, maxSize) + biggestMinBinaryHeap(T->left->right, maxSize);
    }
    if (T->right != nullptr) {
        if (T->value > T->right->value) return false;
        rightSize = 1 + biggestMinBinaryHeap(T->right->left, maxSize) + biggestMinBinaryHeap(T->right->right, maxSize);
    }
 
    int size = 1 + leftSize + rightSize;
    if (size > maxSize) maxSize = size;
    return size == (1 << int(log2(size) + 1)) - 1;
}
 
int biggestMinBinaryHeap(node* T) {
    int maxSize = 0;
    biggestMinBinaryHeap(T, maxSize);
    return maxSize;
}
//1c
 
 
bool isBoth(node* T, int minValue, int maxValue) {
    if (T == nullptr) return true;
 
    if (T->value < minValue || T->value > maxValue) return false;
 
    bool leftIsValid = isBoth(T->left, minValue, T->value);
    bool rightIsValid = isBoth(T->right, T->value, maxValue);
 
    return leftIsValid && rightIsValid;
}
 
bool isBoth(node* T) {
    return false // deoarece nu poate sa fie si BST si min-heap
}
 
//1d
 
 node *createNode(int i)
{
          node *p = new node;
          p->value = i;
          p->left = nullptr;
          p->right = nullptr;
          return p;
}

int main() {
    node* T = createNode(19);
    T->left = createNode(5);
    T->right = createNode(15);
    T->left->left = createNode(1);
    T->left->right = createNode(7);
    T->right->left = createNode(12);
    T->right->right = createNode(20);
 
    if (isBoth(T)) {
        std::cout << "The binary tree is both a min-heap and a binary search tree." << std::endl;
    } else {
        std::cout << "The binary tree is not both a min-heap and a binary search tree." << std::endl;
    }
 
    return 0;
}




bool isTree(vector<int> &v)
{
    // if parent doesnt exist
    int n = v.size();
    for (int i = 0; i < n; i++)
    {
        if (v[i] < -1 || v[i] >= n)
            return false;
    }
    
    // check that it can reach root
    for (int i = 0; i < n; i++)
    {
        if (v[i] == -1)
            continue;
 
        int j = v[i];
        while (j != -1)
        {
            if (j == i)
                return false;
            j = v[j];
        }
    }
 
    return true;
}
 
// 2b
bool isBinHeap(vector<int> arr)
{
    int n = arr.size()
    for (int i=0; i<=(n-2)/2; i++)
    {
        // If left child is greater, return false
        if (arr[2*i +1] > arr[i])
                return false;
  
        // If right child is greater, return false
        if (2*i+2 < n && arr[2*i+2] > arr[i])
                return false;
    }
    return true;
}
 
// 2c
 
bool isPreorder(const vector<int>& p) {
    // ascending sequences
    int n = p.size();
    int i = 0;
    while (i < n) {
        int right = i + 1;
        while (right < n && p[right] > p[i]) {
            right++;
        }
        for (int j = i + 1; j < right; j++) {
            if (p[j] < p[i]) {
                return false;
            }
        }
        i = right;
    }
    return true;
}

int main()
{
    vector<int> v = {-1, 0, 1, 2, 3};

    cout << isTree(v);
    cout << isBinHeap(v);
    cout << isPreorder(v);
    return 0;
}