Examples | BinarySearchTree.h

Basic usage

Start with an initializer list, insert one more value, erase a value, and iterate in sorted order.

C++

BinarySearchTree<int> tree = {8, 3, 10, 1, 6, 14, 4, 7, 13};
tree.insert(5);
tree.erase(10);

for (int value : tree) {
    std::cout << value << ' ';
}

Custom comparator

Define ordering outside the value type when you want descending order or domain-specific sorting.

C++

struct DescendingInt {
    bool operator()(int lhs, int rhs) const {
        return lhs > rhs;
    }
};

BinarySearchTree<int, DescendingInt> tree;
tree.insert(10);
tree.insert(5);
tree.insert(20);

Custom object

Use emplace with a custom type and comparator when storing richer records.

C++

struct Book {
    std::string title;
    int year;
};

struct BookTitleLess {
    bool operator()(const Book& lhs, const Book& rhs) const {
        return lhs.title < rhs.title;
    }
};

BinarySearchTree<Book, BookTitleLess> library;
library.emplace(Book{"Dune", 1965});
library.emplace(Book{"Foundation", 1951});

Iterator usage

Iterators support ordered traversal, bound queries, and erase-by-position.

C++

auto lower = tree.lower_bound(23);
auto upper = tree.upper_bound(25);
auto next = tree.erase(tree.find(25));

Traversal usage

Traversal helpers accept lambdas or other callable objects.

C++

tree.in_order_traversal([](const int value) {
    std::cout << value << ' ';
});

tree.pre_order_traversal([](const int value) {
    std::cout << value << ' ';
});

Compile commands

Bash

g++ -std=c++17 -Wall -Wextra -Wpedantic examples/basic_usage.cpp -Iinclude -o basic_usage
g++ -std=c++17 -Wall -Wextra -Wpedantic examples/custom_object.cpp -Iinclude -o custom_object
g++ -std=c++17 -Wall -Wextra -Wpedantic examples/iterator_usage.cpp -Iinclude -o iterator_usage
g++ -std=c++17 -Wall -Wextra -Wpedantic examples/traversal_usage.cpp -Iinclude -o traversal_usage