I used this code to perform this kind of operation.
Code:
int BST(Treeptr p, int MIN, int MAX);
int ordtree_old(Treeptr p) {
/* BST = Binary Search Tree.
* You can name your function as you wish.
* INT_MIN is the minimum value an integer
* can take. Imagine it as -infinity.
* We use -oo, to actually do what we did before,
* just by eyeballing the tree, to see if all the
* values are OK.
*/
return BST(p, INT_MIN, INT_MAX);
}
int BST(Treeptr p, int MIN, int MAX) {
/* Function was called from some leaf, so p
* is NULL. We should place that here, because
* we do not want to process further a NULL pointer.
* I mean what if we do p.value? That would be an
* error.
*/
if (p == NULL)
return 1;
if (
/* current value is greater than the min value */
p->value > MIN
/* current value is less than the max value */
&& p->value < MAX
/* We set the left child as the root, MIN does not
* need to be updated. MAX is the minimum value between
* current value and MAX. */
&& BST(p->left, MIN, min(p->value, MAX))
/* We set the right child as the root, MAX does not
* need to be updated. MIN is the maximum value between
* current value and MIN. */
&& BST(p->right, max(p->value, MIN), MAX))
return 1;
else
return 0;
}
However, on the test of a course, I saw that it was requested to do this with this "code" (.....GAP A.....) and so on are the parts needed to be filled):
Code:
int ordtree(Treeptr p)
{ int a, b;
return (p == NULL || fun(p, &a, &b)); }
int fun(Treeptr p, .....GAP A.....)
{ int a, b;
if (p->left == NULL && .....GAP B.....) {
*ap = p->value;
.....GAP C..... }
if (p->right == NULL) {
*bp = p->value;
return (fun(.....GAP D.....) && p->value > b); }
if (.....GAP E.....) {
.....GAP F.....
return (fun(p->right, &a, bp) && GAP .....G.....); }
return (.....GAP H.....); }
I got very confused with the variables a and b inside fun(). I tried some things and here is my last attempt:
Code:
int fun(Treeptr p, int* ap, int* bp)
{ int a, b;
if (p->left == NULL && .....GAP B.....) {
*ap = p->value;
.....GAP C.....}
if (p->right == NULL) {
*bp = p->value;
return (fun(p->left, ap, &b) && p->value > b);}
if (p->value < *ap) {
a = *ap;
return (fun(p->right, &a, bp) && p->value < a);}
return 0;
}
However I feel it's not correct. I would like some guidance here.