CODEWITHSUNDEEP
cbinary-search-treeordered-tree
gsamaras
gsamaras

Reputation: 73366

Function to determine if tree is ordered (i.e. a BST)

I have these functions to determine if a binary tree is ordered or not.

(It is assumed that we already have implemented the treemanagement.c, which I have modified to host integers and not strings)

int ordtree(Treeptr p) {
  int a, b;
  return (p == NULL || fun(p, &a, &b));
}

int fun(Treeptr p, int * ap, int * bp) {
  int a, b;
  // Is 'p' a leaf?
  if (p->left == NULL && p->right == NULL) {
    *ap = p->value;
    return 1;
  }

  // Does 'p' have only a left child?
  if (p->right == NULL) {
    *bp = p->value;
    return (fun(p->left, &b, ap) && p->value > b);
  }

  // Does 'p' have only a right child?
  if (p->left == NULL) {
    *ap = p->value;
    return (fun(p->right, &a, bp) && p->value < a);
  }

  // 'p' has two children
  return (fun(p->right, &a, bp) && fun(p->left, &b, ap));
}

The problem is that this will not work for a perfect tree (all nodes have two children, because there is no value checking in the case of a perfect tree in my code!).

For example, this unordered tree will be evaluated as an ordered one!

     4
  2      6
1   8  5   7

A bigger problem is that this comes from a test and I am obliged to use this "code" and fill in the GAPs.

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.....);
}

Any guidance?

Upvotes: 0

Views: 144

Answers (1)

Jason Hu
Jason Hu

Reputation: 6333

this is the best code i can do.

int fun(Treeptr p, int * ap, int * bp) {
  int a, b;
  // Is 'p' a leaf?
  if (p->left == NULL && p->right == NULL) {
    *ap = p->value;
    *bp = p->value; return 1; //gap c
  }

  // Does 'p' have only a left child?
  if (p->right == NULL) {
    *bp = p->value;
    return (fun(p->left, ap, &b) && p->value > b); //gap d
  }

  // Does 'p' have only a right child?
  if (p->left == NULL) {
    *ap = p->value;
    return (fun(p->right, &a, bp) && p->value < a); // gap g
  }

  // 'p' has two children
  return (fun(p->right, &a, bp) && fun(p->left, ap, &b) && a > p->value && p->value > b); // gap h
}

Upvotes: 1

Related Questions