Remove all nodes that satisfy a condition from a binary tree

Question

Assume a binary tree with a data structure like this:

typedef struct binary_node BINARY_NODE;
#define BINARY_NODE BINARY_NODE

struct binary_node {
    BINARY_NODE *next[2]; /* 0 -> left */
};

Assume insertions maintain a relevant order, but there is no balancing criteria.

removeBinaryNode() takes a node and its parent as input, and removes the provided node.

BINARY_NODE *
findLeftmostBinaryNode (BINARY_NODE *node)
{
    assert(node);
    while (node->next[0]) {
        node = node->next[0];
    }
    return node;
}

/* Returns the removed node (caller frees if needed). */
BINARY_NODE *
removeBinaryNode (BINARY_NODE *node, BINARY_NODE *parent)
{
    assert(node && parent);
    assert(parent->next[0] == node || parent->next[1] == node);

    int from = (parent->next[1] == node);

    /* At most one child. The node's child takes node's place. */
    if (node->next[0] == NULL || node->next[1] == NULL) {
        int next = (node->next[0] == NULL);
        parent->next[from] = node->next[next];
        node->next[0] = node->next[1] = NULL;
        return node;
    }

    /* Merge left subtree with right subtree, reduces problem
       to previous case. */
    BINARY_NODE *leftmost = findLeftmostBinaryNode(node->next[1]);
    assert(leftmost->next[0] == NULL);
    leftmost->next[0] = node->next[0];
    parent->next[from] = node->next[1];
    node->next[0] = node->next[1] = NULL;
    return node;
}

The following data structure provides a stateful predicate mechanism.

typedef struct binary_node_predicate BINARY_NODE_PREDICATE;
#define BINARY_NODE_PREDICATE BINARY_NODE_PREDICATE 

struct binary_node_predicate {
    bool (*test)(BINARY_NODE_PREDICATE *, BINARY_NODE *);
};

pruneBothSidesBinaryNode() assumes the current node is already discounted for pruning, and prunes each of the left and right subtrees of the current node.

void pruneOneSideBinaryNode (
        int, BINARY_NODE *, BINARY_NODE_PREDICATE *);

void
pruneBothSidesBinaryNode (BINARY_NODE *current, BINARY_NODE_PREDICATE *pred)
{
    /* current's removal already ruled out */
    if (current == NULL) return;

    pruneOneSideBinaryNode(0, current, pred);
    pruneOneSideBinaryNode(1, current, pred);
}

void
pruneOneSideBinaryNode (
        int side, BINARY_NODE *parent, BINARY_NODE_PREDICATE *pred)
{
    while (parent->next[side] && pred->test(pred, parent->next[side])) {
        free(removeBinaryNode(parent->next[side], parent));
    }
    pruneBothSidesBinaryNode(parent->next[side], pred);
}

The root of the binary tree is actually just another BINARY_NODE. The removeAllIfBinaryNode() wraps a BINARY_NODE with a dummy parent so that the root can be treated as the child of a parent.

void
removeAllIfBinaryNode (BINARY_NODE **root, BINARY_NODE_PREDICATE *pred)
{
    BINARY_NODE dummy = { { (root ? *root : NULL), NULL } };

    assert(root);
    if (*root == NULL) return;

    pruneOneSideBinaryNode(0, &dummy, pred);
    *root = dummy.next[0];
}

---

Example

This is a generic binary tree interface. The usage would use membership of BINARY_NODE into the client's data structure.

struct my_node {
    BINARY_NODE base;
    int key;
    int value;
};

We can then hypothetically assume the existence of APIs that allowed a binary tree consisting of my_nodes to be created, even though the APIs manipulate BINARY_NODE.

BINARY_NODE_PREDICATE can be used to implement a stateful callback. It is not as useful for a stateless callback where a simple callback function pointer would have been sufficient. However, consider the case where there was a threshold to decide whether or not to delete an element, and the threshold was decided at runtime.

struct meets_threshold_predicate {
    BINARY_NODE_PREDICATE base;
    int threshold;
};

bool
meetsThreshold (BINARY_NODE_PREDICATE *pred, BINARY_NODE *node)
{
    struct meets_threshold_predicate *p = (void *)pred;
    struct my_node *n = (void *)node;
    return n->value > p->threshold;
}

void
removeMyNodesAboveThreshold (struct my_node **root, int threshold)
{
    struct meets_threshold_predicate p = {
        { meetsThreshold },
        threshold
    };

    BINARY_NODE *base = &(*root)->base;
    removeAllIfBinaryNode(&base, &p.base);
    *root = (void *)base;
}

Answer 1

I see a number of things which may help you improve your code.

Make sure you have all required #includes

The code uses assert but doesn't #include <assert.h> and uses bool but doesn't #include <stdbool.h>. Also, carefully consider which #includes are part of the interface (and belong in the .h file) and which are part of the implementation.

Eliminate unneeded #defines

The code currently includes a couple of pairs like this:

typedef struct binary_node BINARY_NODE;
#define BINARY_NODE BINARY_NODE

The second line is redundant and should be eliminated.

Use better naming

Don't use all caps, such as BINARY_NODE for a typedef. By old and popular convention, such names are used only for #defined constants.

Combine typedef with struct declaration

Instead of having two separate statements like this:

typedef struct binary_node_predicate BINARY_NODE_PREDICATE;

struct binary_node_predicate {
    bool (*test)(BINARY_NODE_PREDICATE *, BINARY_NODE *);
};

I would normally combine them like this:

typedef struct binary_node_predicate {
    bool (*test)(struct binary_node_predicate *, BINARY_NODE *);
} BINARY_NODE_PREDICATE;

Note that this means that the alternate name can't be used within the declaration, but for me, it makes it more clear. One could make the argument that the two-statement version allows consistency of naming, but in my judgement, having relevant information all in one place trumps that.

Clarify the contract

If I were going to use this code, it would not be entirely clear how to do it. For instance, what if I want to add data to the structure (see next suggestion)? Can I pass in a NULL pointer, and if so, what happens? All of these things are part of the "contract" between the library provider and the user, even if these are the same person. Making the roles and responsibilities of each more clear helps to prevent programming errors and inefficiencies.

Think of the user

If one were going to usefully reuse this code, the tree nodes would probably have to contain something other than just links to other nodes. For that reason, I'd recommend against attempting to create a node as is done within removeAllIfBinaryNode:

BINARY_NODE dummy = { { (root ? *root : NULL), NULL } };

The problem is that if we redefine BINARY_NODE to contain some data, say, like this:

struct binary_node {
    int n;
    BINARY_NODE *next[2]; /* 0 -> left */
};

then the initialization will fail because it doesn't include the int n portion. Better would be to restructure the code to use the **root directly, or to require that the user also provide a function which creates a default node.

Pass a function instead of a structure

The current predicate definition is odd. For instance, I made the change to the binary tree shown above, adding an int member and created a simple tree containing the integers 1 through 7. I then wrote a predicate to eliminate all nodes that contained an integer that was divisible by three:

bool divByThree(BINARY_NODE_PREDICATE *pred, BINARY_NODE *node) {
    return node ? node->n % 3 == 0 : false;
}

Then I used it like this:

BINARY_NODE_PREDICATE pred = { divByThree };
removeAllIfBinaryNode(&root, &pred);

It's not clear to me why the predicate needs to refer to itself, nor why it isn't declared as a function rather than as a structure containing a function. I'd have expected something more like this:

bool divByThree(BINARY_NODE *node) {
    return node ? node->n % 3 == 0 : false;
}

removeAllIfBinaryNode(&root, divByThree);

Consider alternative memory schemes

Deleting nodes in this case consists of calling free on each node. For this to work, each node must have been malloc'd at creation. For small data structures like this, this is often a very inefficient memory allocation scheme. Instead, I'd suggest that the user should be required to provide a node deleter that would be called everywhere you currently call free.