Binary search tree traversal in C

October 9, 2022

I have this function that traverses a binary search tree and appends nodes to a list if they are between a given lower and upper bound.

// n - the current node
// l - a list to accumulate results
static void doTreeSearchBetween(Tree t, Node n, Record lower,
                                Record upper, List l) {
    // empty tree
    if (n == NULL) {
        return;
    } 
    int cmpUpper = t->compare(n->rec, upper);
    int cmpLower = t->compare(n->rec, lower);

    // search left subtree
    doTreeSearchBetween(t, n->left, lower, upper, l);

    // if node if between lower and upper records append to list
    if (cmpLower >= 0 && cmpUpper <= 0) {
        ListAppend(l, n->rec);
    }

    // search right subtree
    doTreeSearchBetween(t, n->right, lower, upper, l);
}

I realised the issue with this code is that it traverses the entirety of the list in-order, making it very inefficient and I’m looking for a way that would allow me to visit as few nodes as possible. The logic isn’t working out for me, I was wondering if anyone had any ideas? I tried adding a couple if statements for whenever the current node is less than the lower and greater than the upper bound, that didn’t work out for me.

An example of the output:

Inserting: 11 13 17 19 23 29 31 37 41 43
Searching between 10 and 20
Search returned: 11 13 17 19

Type defs:

typedef struct node *Node;
struct node {
    Record rec;
    Node   left;
    Node   right;
};

struct tree {
    Node    root;
    int     (*compare)(Record, Record);
};

struct list {
    Record *items;
    int     numItems;
    int     maxItems;
};


struct record {
    char familyName[MAX_FAMILY_NAME_LENGTH + 1];
    char givenName[MAX_GIVEN_NAME_LENGTH + 1];
};

>Solution :

You should rely on the comparisons to determine whether to recurse on the left and/or right branches:

if the tree node is below the lower bound, its left subtree can be pruned.
if the tree node is above the upper bound, its right subtree can be pruned.

Assuming it is empty at the root node, the list will be sorted by construction.

// n - the current node
// l - a list to accumulate results
static void doTreeSearchBetween(Tree t, Node n, Record lower,
                                Record upper, List l) {
    // empty tree
    if (n == NULL) {
        return;
    } 
    int cmpUpper = t->compare(n->rec, upper);
    int cmpLower = t->compare(n->rec, lower);

    if (cmpLower >= 0) {
       // search left subtree
       doTreeSearchBetween(t, n->left, lower, upper, l);

       // if node if between lower and upper records append to list
       if (cmpUpper <= 0) {
           ListAppend(l, n->rec);
       }
    }
    if (cmpUpper <= 0) {
       // search right subtree
       doTreeSearchBetween(t, n->right, lower, upper, l);
    }
}