Search

Lesson 10 of 16 in Coddy's AVL Tree - Data Structures Series #10 course.

Because the tree is always a valid binary search tree (balancing never breaks the ordering), searching it is exactly like searching a plain BST: start at root, and at each node go left if the target is smaller, right if it's larger, or stop if it matches. Reaching a null pointer means the value isn't in the tree.

Since balancing keeps the height around log(n) no matter how values are inserted, this search never degrades to a slow linear scan, unlike an unbalanced BST built from sorted input.

Challenge

Beginner

Write a method search(value) on AVLTree that returns true if value exists anywhere in the tree, false otherwise.

Try it yourself

#include <stdio.h>
#include <string.h>
#include "avltree.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char cmd[32];
        int arg;
        int parsed = sscanf(line, "%31s %d", cmd, &arg);
        if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
            AVLTree_insert(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "search") == 0) {
            if (AVLTree_search(tree, arg)) {
                printf("true\n");
            }
            if (!AVLTree_search(tree, arg)) {
                printf("false\n");
            }
        }
    }
    return 0;
}