#embody <bits/stdc++.h>
utilizing namespace std;
struct Node {
int knowledge;
Node* left;
Node* proper;
Node(int num)
{
knowledge = num;
left = NULL;
proper = NULL;
}
};
int goal, ans;
unordered_map<Node *, int> minv, maxv, h, sum;
bool isBST(Node* root)
{
if (root == NULL)
return true;
if (root->left == NULL
and root->proper == NULL) {
minv[root] = root->knowledge;
maxv[root] = root->knowledge;
h[root] = 1;
sum[root] = root->knowledge;
if (sum[root] == goal)
ans = min(ans, h[root]);
return true;
}
if (root->left == NULL) {
if (isBST(root->proper)
and minv[root->right] > root->knowledge) {
minv[root] = root->knowledge;
maxv[root] = maxv[root->right];
h[root] = h[root->right] + 1;
sum[root] = sum[root->right] + root->knowledge;
if (sum[root] == goal)
ans = min(ans, h[root]);
return true;
}
return false;
}
if (root->proper == NULL) {
if (isBST(root->left)
and maxv[root->left] < root->knowledge) {
minv[root] = minv[root->left];
maxv[root] = root->knowledge;
h[root] = h[root->left] + 1;
sum[root] = sum[root->left] + root->knowledge;
if (sum[root] == goal)
ans = min(ans, h[root]);
return true;
}
return false;
}
bool bstleft = isBST(root->left);
bool bstright = isBST(root->proper);
if (bstleft and bstright
and maxv[root->left] < root->knowledge
and minv[root->right] > root->knowledge) {
minv[root] = minv[root->left];
maxv[root] = maxv[root->right];
h[root] = 1 + h[root->left] + h[root->right];
sum[root] = root->knowledge + sum[root->left]
+ sum[root->right];
if (sum[root] == goal)
ans = min(ans, h[root]);
return true;
}
return false;
}
int minSubtreeSumBST(int okay, Node* root)
{
ans = INT_MAX;
goal = okay;
isBST(root);
if (ans == INT_MAX)
return -1;
return ans;
}
int fundamental()
{
int okay = 38;
Node* root = new Node(13);
root->left = new Node(5);
root->proper = new Node(23);
root->left->proper = new Node(17);
root->left->right->left = new Node(16);
int res = minSubtreeSumBST(okay, root);
cout << res << endl;
return 0;
}
