Binary search tree traversal in C

Question

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];
};

Answer 1

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);
    }
}