BFS and DFS

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct tree tree;
struct tree {
  int data;
  tree *left, *right;
};
static tree *tree_new(int data) {
  tree *new = calloc(1, sizeof(*new));
  new->data = data, new->left = new->right = NULL;
  return new;
}
static void tree_free(tree *t) {
  if (!t) { return; }
  tree_free(t->left), tree_free(t->right), free(t);
}
static tree *tree_insert(tree *t, int x) {
  if (!t) { return tree_new(x); }
  if (x < t->data) {
    t->left = tree_insert(t->left, x);
  } else if (t->data < x) {
    t->right = tree_insert(t->right, x);
  }
  return t;
}
static void tree_inorder(tree *t) {
  if (!t) { return; }
  tree_inorder(t->left), printf("%3d", t->data), tree_inorder(t->right);
}
static void tree_show(tree *t, int level) {
  if (!t) { return; }
  tree_show(t->left, level + 1);
  for (int i = 0; i < level; ++i) {
    fputs((i < level - 1 ? "    " : " ---"), stdout);
  }
  printf("%d\n", t->data);
  tree_show(t->right, level + 1);
}
static int randint(int max) {
  static bool first = true;
  if (first) { srand(time(NULL)), first = false; }
  return rand() % max;
}
typedef struct entry entry;
struct entry {
  tree *tree;
  entry *next;
};
typedef struct {
  entry *head, *tail;
} stack_queue;
static entry *entry_new(tree *t) {
  entry *new = calloc(1, sizeof(*new));
  new->tree = t, new->next = NULL;
  return new;
}
static stack_queue *queue_new(void) {
  stack_queue *new = calloc(1, sizeof(*new));
  new->head = new->tail = NULL;
  return new;
}
static bool queue_is_empty(stack_queue *q) { return !q->head; }
static void queue_enqueue(stack_queue *q, tree *t) {
  if (!t) { return; }
  entry *new = entry_new(t);
  if (queue_is_empty(q)) {
    q->head = q->tail = new;
    return;
  }
  q->tail->next = new, q->tail = new;
}
static void entry_free(entry *e) {
  if (!e) { return; }
  entry_free(e->next), free(e);
}
static tree *queue_dequeue(stack_queue *q) {
  if (queue_is_empty(q)) { return NULL; }
  entry *e = q->head;
  q->head = e->next, e->next = NULL;
  tree *t = e->tree;
  entry_free(e);
  return t;
}
static void queue_free(stack_queue *q) {
  if (!q) { return; }
  entry_free(q->head);
  free(q);
}
static stack_queue *stack_new(void) { return queue_new(); }
static bool stack_is_empty(stack_queue *s) { return queue_is_empty(s); }
static void stack_push(stack_queue *s, tree *t) {
  if (!t) { return; }
  entry *new = entry_new(t);
  if (stack_is_empty(s)) {
    s->head = s->tail = new;
    return;
  }
  new->next = s->head, s->head = new;
}
static tree *stack_pop(stack_queue *s) { return queue_dequeue(s); }
static void stack_free(stack_queue *s) { queue_free(s); }
static tree *bfs(tree *t, int x) {
  stack_queue *q = queue_new();
  tree *found;
  for (queue_enqueue(q, t); !queue_is_empty(q);
       queue_enqueue(q, found->left), queue_enqueue(q, found->right)) {
    found = queue_dequeue(q), printf("%d... ", found->data);
    if (found->data == x) {
      puts("!"), queue_free(q);
      return found;
    }
  }
  puts(""), queue_free(q);
  return NULL;
}
static tree *dfs(tree *t, int x) {
  stack_queue *s = stack_new();
  tree *found;
  for (stack_push(s, t); !stack_is_empty(s);
       stack_push(s, found->left), stack_push(s, found->right)) {
    found = stack_pop(s), printf("%d... ", found->data);
    if (found->data == x) {
      puts("!"), stack_free(s);
      return found;
    }
  }
  puts(""), stack_free(s);
  return NULL;
}
int main(void) {
  int n = 15, max = 100, x = 0;
  tree *root = NULL;
  for (int i = 0, r = randint(max); i < n; ++i, r = randint(max)) {
    if (i == n / 2) { x = r; }
    root = tree_insert(root, r);
  }
  tree_inorder(root), puts("");
  tree_show(root, 0);
  printf("BFS(%d): ", x), bfs(root, x);
  printf("DFS(%d): ", x), dfs(root, x);
  printf("BFS(%d): ", max), bfs(root, max);
  printf("DFS(%d): ", max), dfs(root, max);
  tree_free(root);
}