Как найти все одинаковые записи в двоичном Б-дереве?

не могу придумать или найти алгоритм с повторяющимися данными в двоичном дереве. Хотя они условно повторяющиеся. В общем, есть БД на 4000 строк с инфой: ФИО, улица, дом, кв, дата заселения. Если смотреть по всем полям совпадений нет. Мне надо вывести всех кто живет на такой-то улице, не ранее такой-то даты. Дерево строил согласно алгоритму, начиная как раз таки с улицы, в memcmp(данные, ключ) > 0 левая ветвь и т.д. Т.е. сравниваем улицы, если совпали -> сравниваем даты, если совпали -> сравниваем фио, таких записей уже нет повторяющихся. А теперь столкнулся с поиском по ключу и не понимаю как это должно работать с повторениями. Алгоритм классический, сравниваем с ключом если меньше то влево, больше вправо. Ну я могу один раз вернуть найденное значение, а остальные по этому же ключу как? Я же не могу указатель без условия ставить на ту или иную ветвь. Весь код наверное нет смысла вписывать.

tree * search_for_key(tree * p, char key_str[], char * key_dat) {// Поиск вершины по ключу
while (p != NULL) {
    if (memcmp(key_str, p->data.street, 20) == 0) { // Пусть пока просто по названию улицы
        prt(p);   // Вывод
        return p; // Один раз вернет запись, потом будет все время крутить это условие
    } // Потому что не переносится указатель дальше, а по какому условию двигаться дальше?
    if (memcmp(key_str, p->data.street, 20) < 0) { // Чтобы вывести все такие записи
        p = p->left;
    }
    else if (memcmp(key_str, p->data.street, 20) > 0) {
        p = p->right;           
    }
}

}

Структуры:

    struct adres_book
{
    char fio[32];
    char street[20];
    unsigned short int home;
    unsigned short int flat;
    char date[8];
} book;

typedef struct tree {
    int id;
    struct adres_book data;
    int balance;
    tree * left;
    tree * right;
};

В общем у меня вариант только А < k <= B, но вычитал что преподаватели не любят этот вариант. Там больше идет обсуждения в целом о наличии одинаковых элементов и обоснованность их присутствия в ДД. А у меня то и записи все уникальны, а организовать поиск чет не могу. Только так

if (memcmp(key_str, p->data.street, 20) < 0) {
        p = p->left;
    }
    else if (memcmp(key_str, p->data.street, 20) > 0 || memcmp(key_str, p->data.street, 20) == 0) {
        if (memcmp(key_str, p->data.street, 20) == 0) {//&& compare(key_dat, p->data.date))
            prt(p);
        }
        p = p->right;           
    }

Может можно по другому? я не могу просто додумать. Этот тоже не работает, выводит 5 записей из 15 совпадений, при n = 100 строк из бд. Такая штука получилась, к - ключ:

Выводит только 22, 17, 4. На индексы не обращайте внимание, дерево построено не них основе. Весь код, может я до этого что-то делаю не так.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <io.h>
#include <Windows.h>

struct adres_book
{
    char fio[32];
    char street[20];
    unsigned short int home;
    unsigned short int flat;
    char date[8];
} book;

typedef struct tree {
    int id;
    struct adres_book data;
    int balance;
    tree * left;
    tree * right;
};

tree * node_new(int ind, adres_book data) { 
    tree * node = new tree;
    if (!node)
        return NULL;
    node->id = ind;
    node->data = data;              
    node->balance = 0;
    node->left = NULL;              
    node->right = NULL;
    return node;
}

tree * left(tree * p, boolean &Vr, boolean &Hr){
    tree * q;
    if (Vr) {
        if (p->balance == 0) {
            q = p->left;
            p->left = q->right;
            q->right = p;
            p = q;
            q->balance = 1;
            Vr = false;
            Hr = true;
        }
        else {
            p->balance = 0;
            Hr = true;
        }
    }
    else {
        Hr = false;
    }
    return p;
}

tree * right(tree * p, boolean &Vr, boolean &Hr) {
    tree * q;
    if (Vr) {
        p->balance = 1;
        Vr = false;
        Hr = true;
    }
    else if (Hr) {
        if (p->balance > 0) {
            q = p->right;
            p->right = q->left;
            p->balance = 0;
            q->balance = 0;
            q->left = p;
            p = q;
            Vr = true;
            Hr = false;
        }
        else {
            Hr = false;
        }
    }
    return p;
}

tree * tree_insert(tree * p, int ind, adres_book data, boolean &Vr, boolean &Hr) {      // Вставка элемента в дерево
    tree * q;
    if (p == NULL) {
        p = node_new(ind, data);
        Vr = true;
        return p;
    }
    if (memcmp(data.street, p->data.street, 20) < 0) {  
        p->left = tree_insert(p->left, ind, data, Vr, Hr);
        p = left(p, Vr, Hr);
    }
    else { 
        p->right = tree_insert(p->right, ind, data, Vr, Hr);
        p = right(p, Vr, Hr);
    }
    return p;
}

void prt(tree * p) {
    printf("%-4.d ", p->id);
    for (int i = 0; i < 32; i++) printf("%c", p->data.fio[i]);
    printf(" ");
    for (int i = 0; i < 20; i++) printf("%c", p->data.street[i]);
    printf(" %3hu %3hu ", p->data.home, p->data.flat);
    for (int i = 0; i < 8; i++) printf("%c", p->data.date[i]);
    printf("\n");
}

void search_for_key(tree * p, char key_str[], char * key_dat) {     // Поиск вершины по ключу
    while (p != NULL) { 
        if (memcmp(key_str, p->data.street, 20) < 0 || memcmp(key_str, p->data.street, 20) == 0) { 
            if (memcmp(key_str, p->data.street, 20) == 0) {//&& compare(key_dat, p->data.date))
                prt(p);
            }
            p = p->left;
        }
        else if (memcmp(key_str, p->data.street, 20) > 0 || memcmp(key_str, p->data.street, 20) == 0) {
            if (memcmp(key_str, p->data.street, 20) == 0) {//&& compare(key_dat, p->data.date))
                prt(p);
            }
            p = p->right;
        }
        else
            break;
    }
}

int main()
{
    FILE * fp = fopen("BASE4.DAT", "rb");
    tree * p = NULL;
    list * h = NULL;
    boolean Hr;                     // Вертикальный рост дерева
    boolean Vr;                     // Горизонтальный рост дерева
    if (fp == NULL) {
        printf("Error File!\n");
        system("pause");
        exit(1);
    }
    int ind = 1;
    while (fread(&book, sizeof(book), 1, fp) == 1) {
        Hr = true;
        Vr = true;
        p = tree_insert(p, ind, book, Vr, Hr);
        ind++;
        puts("");
        if (ind == 30)
            break;
    }
    
    char search_street[20] = {};
    printf("\nEnter key street: ");
    scanf("%s", search_street);
    search_for_key(p, search_street, search_date);
    fclose(fp);
    system("pause");
}