class _Node:
    """Single node of a tree. Keeps references to parent, left, right and some data."""
    pass

class Tree:
    """Tree itself. Keeps root node of a tree and a comparision function."""
    pass

def create(cmp_func):
    """Create empty tree."""
    ...

def clear(tree):
    """Clear tree but do not destroy tree itself."""
    ...

def size(tree):
    """Return number of elements."""
    ...

def find(tree, data):
    """Find element with equal data and return its data if any."""
    ...

def insert(tree, data):
    """Insert data into tree and return replaced data if any."""
    ...

def delete(tree, data):
    """Delete element with equal data and return its data if any."""
    ...

def foreach(tree, func):
    """Call func for every element's data in tree in infix-order."""
    ...

typedef void * Pointer;

typedef int (*CmpFunc)(Pointer data1, Pointer data2);

typedef struct tBSTNode {
    Pointer data;
    /* ... */
} BSTNode;

typedef struct tBST {
    BSTNode *root;
    CmpFunc cmp_func; /* all data comparisons should be done
                         with help of this func! */
    /* ... */
} BST;

// Create empty tree
BST * bst_create(CmpFunc cmp_func);

// Clear tree but do not destroy tree struct
void bst_clear(BST *tree);

// Completely destroy tree
void bst_destroy(BST *tree);

size_t bst_size(BST *tree);

// Find element with equal data and return its data if any else NULL
Pointer bst_find(BST *tree, Pointer data);

// Return data which was replaced by this insertion if any else NULL
Pointer bst_insert(BST *tree, Pointer data);

// Delete node with equal data and return its data if any else NULL
Pointer bst_delete(BST *tree, Pointer data);

// Call foreach_func for every node's data in tree passing given extra_data
void bst_foreach(BST *tree,
                 void (*foreach_func)(Pointer data, Pointer extra_data),
                 Pointer extra_data);

typedef struct tEntry {
    Pointer key;
    Pointer value;
}