Skip to content

Instantly share code, notes, and snippets.

@eduardoleon
Last active November 5, 2019 02:01
Show Gist options
  • Save eduardoleon/530aff34c20f6300017b0558b35900bb to your computer and use it in GitHub Desktop.
Save eduardoleon/530aff34c20f6300017b0558b35900bb to your computer and use it in GitHub Desktop.
#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");
}
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)
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
>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment