int tester(arbre a) {
  int res;
  printf("DEBUT\n");
  if(a==NULL) {
    res = 1;
    printf("1 - 1\n");
    return res;
  }
  else {
    if((a->droit==NULL) && (a->gauche==NULL)) {
      res = 1;
      printf("1 - 2\n");
      return res;
    }
    else {
      if(((a->gauche != NULL) && (a->val > a->gauche->val)) || ((a->droit != NULL) && (a->val > a->droit->val))) {
        res = 0;
        printf("0\n");
        return res;
      }
      else {
        if(res!=0) {
          if(a->gauche!=NULL) {
            printf("Test arbre gauche\n");
            tester(a->gauche);
          }
          if(a->droit!=NULL) {
            printf("Test arbre droit\n");
            tester(a->droit);
          }
        }
      }
    }
  }
  return res;
}

Resultat :
DEBUT
Test arbre gauche
DEBUT
0
Test arbre droit
DEBUT
Test arbre gauche
DEBUT
1 - 2
Test arbre droit
DEBUT
Test arbre droit
DEBUT
1 - 2
-1