Public C++ container reference

Prototype

template <typename T, typename Compare = std::less<T>>
class BinarySearchTree;

Description

Stores unique values in comparator order using a plain Binary Search Tree with smart-pointer-managed nodes.

Parameters

Return value

Not applicable.

Complexity

Example

BinarySearchTree<int> tree;
tree.insert(8);
tree.insert(3);

Notes

• This is not a self-balancing tree.
• Values are unique; equivalent insertions are ignored.

See also

Prototype

explicit BinarySearchTree(const Compare& compare = Compare());

Description

Constructs an empty tree using the supplied comparator object.

Parameters

Return value

None.

Complexity

Example

BinarySearchTree<int> ascending;
BinarySearchTree<int, std::greater<int>> descending;

Notes

The default comparator is std::less<T>.

See also

Prototype

template <typename InputIt>
BinarySearchTree(InputIt first, InputIt last, const Compare& compare = Compare());

BinarySearchTree(std::initializer_list<T> init, const Compare& compare = Compare());

Description

Constructs a tree by inserting every value from a range or initializer list.

Parameters

Return value

None.

Complexity

Example

std::vector<int> values = {8, 3, 10, 1, 6};
BinarySearchTree<int> from_range(values.begin(), values.end());
BinarySearchTree<int> from_list = {8, 3, 10, 1, 6};

Notes

Equivalent values are ignored during construction.

See also

Prototype

BinarySearchTree(const BinarySearchTree& other);
BinarySearchTree(BinarySearchTree&& other) noexcept;
BinarySearchTree& operator=(const BinarySearchTree& other);
BinarySearchTree& operator=(BinarySearchTree&& other) noexcept;
void swap(BinarySearchTree& other);

Description

Supports deep-copy semantics, move transfer, and constant-time swaps of tree ownership.

Parameters

Return value

The assignment operators return a reference to the current tree. Constructors and swap return nothing.

Complexity

Example

BinarySearchTree<int> source = {8, 3, 10};
BinarySearchTree<int> copy(source);
BinarySearchTree<int> moved(std::move(source));

BinarySearchTree<int> other = {1, 2};
copy.swap(other);

Notes

• Copying duplicates the full node structure.
• Moving leaves the source tree empty.

See also

Prototype

size_type size() const noexcept;
bool empty() const noexcept;

Description

Query the current element count and whether the tree contains any values.

Parameters

None.

Return value

• size() returns the current number of values.
• empty() returns true when the tree holds no values.

Complexity

Example

BinarySearchTree<int> tree = {8, 3, 10};
auto count = tree.size();
bool no_values = tree.empty();

Notes

These methods rely on the internal size counter rather than traversing the tree.

See also

Prototype

void clear() noexcept;

Description

Removes all nodes from the tree and resets the size to zero.

Parameters

None.

Return value

None.

Complexity

Example

BinarySearchTree<int> tree = {8, 3, 10};
tree.clear();

Notes

After clear(), begin() == end() and size() == 0.

See also

Prototype

std::pair<iterator, bool> insert(const T& value);
std::pair<iterator, bool> insert(T&& value);

template <typename InputIt>
void insert(InputIt first, InputIt last);

template <typename... Args>
std::pair<iterator, bool> emplace(Args&&... args);

Description

Insert individual values, a range of values, or construct values in place. Equivalent values are not duplicated.

Parameters

Return value

• Single-value insert and emplace return {iterator, bool}.
• The range overload returns nothing.

Complexity

Example

BinarySearchTree<int> tree;
auto [it, inserted] = tree.insert(8);

std::vector<int> values = {3, 10, 1, 6};
tree.insert(values.begin(), values.end());

tree.emplace(14);

Notes

The bool result is false when an equivalent value already exists.

See also

Prototype

size_type erase(const T& value);
iterator erase(const_iterator position);

Description

Removes a matching value by key or erases the value referred to by an iterator.

Parameters

Return value

• Key-based erase returns 1 on success, 0 when nothing matched.
• Iterator-based erase returns the next valid iterator or end().

Complexity

Example

BinarySearchTree<int> tree = {8, 3, 10, 1, 6};
tree.erase(3);

auto it = tree.find(8);
auto next = tree.erase(it);

Notes

• Two-child erase is handled safely by moving nodes rather than erasing via a moved-from key.
• The iterator return value never points to the deleted node.

See also

Prototype

iterator find(const T& value);
const_iterator find(const T& value) const;
bool contains(const T& value) const;

Description

Search for a value and return an iterator, const iterator, or a boolean existence check.

Parameters

Return value

• find() returns an iterator to the matching value or end()/cend().
• contains() returns true when a match exists.

Complexity

Example

BinarySearchTree<int> tree = {8, 3, 10};
auto it = tree.find(3);
bool has_ten = tree.contains(10);

Notes

The const overload of find() is useful when iterating over a const tree.

See also

Prototype

iterator lower_bound(const T& value);
const_iterator lower_bound(const T& value) const;
iterator upper_bound(const T& value);
const_iterator upper_bound(const T& value) const;

Description

Return iterators to the first value not ordered before the key or the first value strictly ordered after it.

Parameters

Return value

Iterator or const iterator to the requested bound, or the past-the-end iterator when no such element exists.

Complexity

Example

BinarySearchTree<int> tree = {8, 3, 10, 6};
auto first_not_before_five = tree.lower_bound(5);
auto first_after_six = tree.upper_bound(6);

Notes

Bounds follow the configured comparator, not necessarily numeric ascending order.

See also

Prototype

iterator begin() noexcept;
const_iterator begin() const noexcept;
const_iterator cbegin() const noexcept;
iterator end() noexcept;
const_iterator end() const noexcept;
const_iterator cend() const noexcept;

Description

Provide mutable and const bidirectional iterators for in-order traversal.

Parameters

None.

Return value

• begin() and cbegin() return the smallest element in comparator order.
• end() and cend() return the past-the-end iterator.

Complexity

Example

for (auto it = tree.begin(); it != tree.end(); ++it) {
    std::cout << *it << ' ';
}

auto last = tree.end();
if (!tree.empty()) {
    --last;
}

Notes

On non-empty trees, --end() yields the largest value.

See also

Prototype

template <typename UnaryFunction>
void in_order_traversal(UnaryFunction&& function) const;

template <typename UnaryFunction>
void pre_order_traversal(UnaryFunction&& function) const;

template <typename UnaryFunction>
void post_order_traversal(UnaryFunction&& function) const;

Description

Visit all values with a callable using in-order, pre-order, or post-order traversal.

Parameters

Return value

None.

Complexity

Example

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

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

Notes

In-order traversal visits values in comparator order.

See also

Prototype

T& min();
const T& min() const;
T& max();
const T& max() const;
size_type height() const noexcept;
std::vector<T> to_vector() const;

Description

Retrieve smallest or largest values, inspect tree height, or export the tree contents to a vector.

Parameters

None.

Return value

• min() and max() return references to stored values.
• height() returns the number of nodes on the longest root-to-leaf path.
• to_vector() returns a vector in comparator order.

Complexity

Example

auto smallest = tree.min();
auto largest = tree.max();
auto tree_height = tree.height();
auto values = tree.to_vector();

Notes

• min() and max() throw std::out_of_range on an empty tree.
• A tall height often indicates unbalanced insertion order.

See also

Prototype

bool is_valid_bst() const;

Description

Verifies that the current node ordering still satisfies the Binary Search Tree property under the configured comparator.

Parameters

None.

Return value

true when the tree is valid, otherwise false.

Complexity

Example

BinarySearchTree<int> tree = {8, 3, 10};
bool valid = tree.is_valid_bst();

Notes

This is primarily a diagnostic helper for tests, debugging, and teaching.

See also