/* C11. binary search tree. Duplicate keys are ignored. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key; struct Node *left, *right; } Node;
static bool insert(Node **root, int key)
{
    while (*root != NULL) {
        if (key == (*root)->key) return true;
        root = key < (*root)->key ? &(*root)->left : &(*root)->right;
    }
    Node *node = malloc(sizeof *node);
    if (node == NULL) return false;
    *node = (Node){key, NULL, NULL}; *root = node;
    return true;
}
static bool contains(const Node *root, int key)
{
    while (root != NULL) {
        if (key == root->key) return true;
        root = key < root->key ? root->left : root->right;
    }
    return false;
}
/* Collect traversals; caller provides capacity at least the number of nodes. */
static void inorder(const Node *r, int out[], size_t *n)
{
    if (r == NULL) return;
    inorder(r->left, out, n); out[(*n)++] = r->key; inorder(r->right, out, n);
}
static void preorder(const Node *r, int out[], size_t *n)
{
    if (r == NULL) return;
    out[(*n)++] = r->key; preorder(r->left, out, n); preorder(r->right, out, n);
}
static void postorder(const Node *r, int out[], size_t *n)
{
    if (r == NULL) return;
    postorder(r->left, out, n); postorder(r->right, out, n); out[(*n)++] = r->key;
}
static void destroy(Node *root)
{
    if (root == NULL) return;
    destroy(root->left); destroy(root->right); free(root);
}
static void show(const char *label, const int out[], const int expected[], size_t n)
{
    printf("%s:", label);
    for (size_t i = 0; i < n; ++i) { assert(out[i] == expected[i]); printf(" %d", out[i]); }
    putchar('\n');
}
int main(void)
{
    Node *root = NULL;
    int keys[] = {40, 20, 60, 10, 30, 50, 70};
    int in[] = {10, 20, 30, 40, 50, 60, 70};
    int pre[] = {40, 20, 10, 30, 60, 50, 70};
    int post[] = {10, 30, 20, 50, 70, 60, 40};
    int out[7]; size_t n = 0;
    assert(!contains(root, 40)); inorder(root, out, &n); assert(n == 0);
    for (size_t i = 0; i < 7; ++i)
        if (!insert(&root, keys[i])) { destroy(root); return EXIT_FAILURE; }
    assert(insert(&root, 40)); assert(contains(root, 50)); assert(!contains(root, 55));
    inorder(root, out, &n); assert(n == 7); show("Inorder", out, in, n);
    n = 0; preorder(root, out, &n); assert(n == 7); show("Preorder", out, pre, n);
    n = 0; postorder(root, out, &n); assert(n == 7); show("Postorder", out, post, n);
    destroy(root); root = NULL; destroy(root);
    assert(insert(&root, 1)); n = 0;
    inorder(root, out, &n); assert(n == 1 && out[0] == 1);
    assert(insert(&root, 2) && insert(&root, 3)); n = 0;
    inorder(root, out, &n); assert(n == 3 && out[0] == 1 && out[2] == 3);
    destroy(root);
    puts("BST tests passed");
    return EXIT_SUCCESS;
}