is_bst.c

#include <stdio.h>
#include <stdlib.h>

struct tree {
     int          value;
     struct tree *left;
     struct tree *right;
};

struct stack {
     int           state;
     struct tree  *node;
     struct stack *next;
};

void create(struct stack **stack)
{
     *stack = NULL;
}

void push(int state, struct tree *node, struct stack **stack)
{
     struct stack *new = malloc(sizeof (struct stack));
     new->state = state;
     new->node  = node;
     new->next  = *stack;
     *stack     = new;
}

int pop(int *state, struct tree **node, struct stack **stack)
{
     struct stack *old = *stack;
     if (!old)
          return 0;
     
     *state = old->state;
     *node  = old->node;
     *stack = old->next;
     free(old);
     return 1;
}

void destroy(struct stack *stack)
{
     struct stack *old;
     while (old = stack) {
          stack = stack->next;
          free(old);
     }
}

void in_order(struct tree *node)
{
     int           state;
     struct stack *stack;
     
     create(&stack);
     push(0, node, &stack);
     
     while (pop(&state, &node, &stack))
          if (!node)
               ;
          else if (!state) {
               push(1, node, &stack);
               push(0, node->left, &stack);
          }
          else {
               printf("%d ", node->value);
               push(0, node->right, &stack);
          }
     
     printf("\n");
}

int is_bst(struct tree *node, int bound)
{
     int           state;
     struct stack *stack;
     
     create(&stack);
     push(0, node, &stack);
     
     while (pop(&state, &node, &stack))
          if (!node)
               ;
          else if (!state) {
               push(1, node, &stack);
               push(0, node->left, &stack);
          }
          else if (bound < node->value) {
               push(0, node->right, &stack);
               bound = node->value;
          }
          else {
               destroy(stack);
               return 0;
          }
     
     return 1;
}

int main()
{
     struct tree nodes[64];
     
     for (int i = 1; i < 32; i++) {
          nodes[i].value = i;
          nodes[i].left  = &nodes[2*i];
          nodes[i].right = &nodes[2*i + 1];
     }
     
     for (int i = 32; i < 64; i++) {
          nodes[i].value = i;
          nodes[i].left  = NULL;
          nodes[i].right = NULL;
     }
     
     in_order(&nodes[1]);
     
     if (is_bst(&nodes[1], 0))
          printf("We have a well-formed BST.\n");
     else
          printf("We have a non-well-formed BST.\n");
}

is_bst.sml

datatype 'a tree = Empty | Tree of 'a tree * 'a * 'a tree
datatype 'a step = Small of 'a | Large of 'a tree

fun loop (_, nil) = true
  | loop (c, Small x :: ss) = if x > c then loop (x, ss) else false
  | loop (c, Large Empty :: ss) = loop (c, ss)
  | loop (c, Large (Tree (a,x,b)) :: ss) = loop (c, Large a :: Small x :: Large b :: ss)

fun is_bst (c, xs) = loop (c, Large xs :: nil)

val good = Tree (Tree (Empty, 2, Tree (Empty, 4, Empty)), 5, Empty)
val bad = Tree (Tree (Empty, 2, Tree (Empty, 7, Empty)), 5, Empty)

session

Poly/ML 5.8 Release
> 
val bad = Tree (Tree (Empty, 2, Tree (Empty, 7, Empty)), 5, Empty): int tree
val good = Tree (Tree (Empty, 2, Tree (Empty, 4, Empty)), 5, Empty): int tree
val is_bst = fn: int * int tree -> bool
val loop = fn: int * int step list -> bool
datatype 'a step = Large of 'a tree | Small of 'a
datatype 'a tree = Empty | Tree of 'a tree * 'a * 'a tree
val it = (): unit
> is_bst (0, good);
val it = true: bool
> is_bst (0, bad);
val it = false: bool
>