Compiler Explorer

Source code

// https://github.com/ulfben/flat_bst/
// flat::bst<T, Compare, IndexT> — a flat, index-based binary search tree
// Stores nodes in a std::vector and links them by integer indices for
// better cache locality, fewer allocations, and stable references.
// Inspired by Jens Weller’s “Looking at binary trees in C++”:
//	 https://meetingcpp.com/blog/items/Looking-at-binary-trees-in-Cpp.html
// Requires C++26. 
// Ulf Benjaminsson, 2025

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <optional>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <vector>

// forward declare the class template so the iterator can name it
namespace flat {
	template<class T, class Compare = std::less<T>, class IndexT = uint32_t>
	class bst;
};

//namespace for the iterator implementation
namespace flat::detail {
	template<class T, class Compare, class IndexT>
	class inorder_iter{
		using tree_t = bst<T, Compare, IndexT>;
		using index_type = IndexT;
		static constexpr index_type npos = tree_t::npos;
		static constexpr size_t traversal_stack_reserve = 16;
		const tree_t* tree_ = nullptr;
		std::vector<index_type> stack_;
		index_type cur_ = npos;

constexpr void push_left_(index_type i){
			while(tree_t::is_valid(i)){
				stack_.push_back(i);
				i = tree_->left_of(i);
			}
		}

public:
		using value_type = const T;
		using reference = const T&;
		using pointer = const T*;
		using difference_type = std::ptrdiff_t;
		using iterator_category = std::forward_iterator_tag;

constexpr inorder_iter() = default;
		explicit constexpr inorder_iter(const tree_t* t, bool end) : tree_(t){
			if(!t || end || !tree_t::is_valid(t->root_index())){ cur_ = npos; return; }
			stack_.reserve(traversal_stack_reserve);
			push_left_(t->root_index());
			cur_ = stack_.back();
			stack_.pop_back();
		}

constexpr reference operator*()  const noexcept{ return tree_->value_of(cur_); }
		constexpr pointer   operator->() const noexcept{ return &tree_->value_of(cur_); }

constexpr inorder_iter& operator++(){
			if(!tree_ || !tree_t::is_valid(cur_)){
				return *this;
			}
			index_type next = tree_->right_of(cur_);
			if(tree_t::is_valid(next)){
				push_left_(next);
			}
			if(stack_.empty()){
				cur_ = npos;
			} else{
				cur_ = stack_.back();
				stack_.pop_back();
			}
			return *this;
		}
		constexpr inorder_iter operator++(int){
			auto tmp = *this;
			++(*this);
			return tmp;
		}

friend constexpr bool operator==(const inorder_iter& a, const inorder_iter& b) noexcept{
			return a.tree_ == b.tree_ && a.cur_ == b.cur_;
		}
		friend constexpr bool operator!=(const inorder_iter& a, const inorder_iter& b) noexcept{
			return !(a == b);
		}
	};
} // namespace flat::detail

namespace flat{
	template<class T, class Compare, class IndexT>
	class bst final{
	public:
		using const_inorder_iterator = flat::detail::inorder_iter<T, Compare, IndexT>;
		using value_type = T;
		using size_type = std::size_t;
		using index_type = IndexT;

static_assert(std::is_unsigned_v<index_type>, "IndexT must be an unsigned integer type");
		static constexpr index_type npos = std::numeric_limits<index_type>::max();

bst() = default;

constexpr explicit bst(Compare cmp) 
			noexcept(std::is_nothrow_move_constructible_v<Compare>) 
			: comp_(std::move(cmp)){}

// if you already have sorted-unique data, create an empty bst and call build_from_sorted_unique instead
		// this ctor just does the right thing for arbitrary ranges.
		template<class It>
		bst(It first, It last, Compare cmp = Compare{})
			: comp_(std::move(cmp)){
			if(first == last){
				return;
			}
			if constexpr(std::random_access_iterator<It>){ // possible fast path if already sorted and unique				
				bool sorted = std::is_sorted(first, last, comp_);
				bool unique = sorted &&
					std::adjacent_find(first, last, [&](const value_type& a, const value_type& b){
					return !comp_(a, b) && !comp_(b, a);
						}) == last;
				if(sorted && unique){
					build_from_sorted_unique(first, last);
					return;
				}
			}
			build_from_range(first, last);
		}

bst(std::initializer_list<value_type> values, Compare cmp = Compare{}) : bst(values.begin(), values.end(), cmp){}

[[nodiscard]] constexpr size_type size() const noexcept{ return alive_; }
		[[nodiscard]] constexpr size_type holes() const noexcept{ return free_.size(); }
		[[nodiscard]] constexpr size_type capacity() const noexcept{ return nodes_.capacity(); }
		[[nodiscard]] constexpr bool empty() const noexcept{ return alive_ == 0; }

//accessors for the iterators to be able to do their work
		//they bloat the public API a bit, but I don't have to deal with friend classes so...
		[[nodiscard]] inline constexpr index_type root_index() const noexcept{ return root_; }
		static inline constexpr bool is_valid(index_type i) noexcept{ return i != npos; }
		[[nodiscard]] inline constexpr index_type left_of(index_type i)  const noexcept{ return get(i).left; }
		[[nodiscard]] inline constexpr index_type right_of(index_type i) const noexcept{ return get(i).right; }
		[[nodiscard]] inline constexpr const value_type& value_of(index_type i) const noexcept{ return get(i).value; }

constexpr void reserve(size_type n){ nodes_.reserve(n); }
		constexpr void rebuild_compact(){ rebalance(); }

constexpr void clear() noexcept{
			nodes_.clear();
			free_.clear();
			root_ = npos;
			alive_ = 0;
		}

void swap(bst& other) noexcept(noexcept(std::swap(comp_, other.comp_))){
			using std::swap;
			swap(root_, other.root_);
			swap(alive_, other.alive_);
			swap(nodes_, other.nodes_);
			swap(free_, other.free_);
			swap(comp_, other.comp_);
		}

// insert / emplace, returns {index, inserted}
		constexpr std::pair<index_type, bool> insert(const value_type& v){
			return insert_impl(v);
		}
		constexpr std::pair<index_type, bool> insert(value_type&& v){
			return insert_impl(std::move(v));
		}
		template<class... Args>
		constexpr std::pair<index_type, bool> emplace(Args&&... args){
			return emplace_impl(std::forward<Args>(args)...);
		}

//bulk insert from range, returns number of inserted elements
		//note: this merges into existing tree, does not rebalance
		template<class It>
		size_type insert(It first, It last){
			if constexpr(std::forward_iterator<It>){
				auto n = static_cast<size_type>(std::distance(first, last));
				if(n) nodes_.reserve(nodes_.size() + n); // best effort
			}
			size_type inserted = 0;
			for(; first != last; ++first){
				inserted += insert(*first).second ? 1 : 0;
			}
			return inserted;
		}

// build balanced tree from pre-sorted-unique input. replacing any existing tree contents
		template<class It>
		void build_from_sorted_unique(It first, It last){
			assert(std::is_sorted(first, last, comp_) && "Input range must be sorted according to Compare");
			bst tmp(comp_);
			tmp.build_from_sorted_unique_into_empty(first, last);
			swap(tmp);
		}

// build balanced tree from arbitrary input range (sorts + uniques)
		template<class It>
		void build_from_range(It first, It last){
			std::vector<value_type> vals;
			if constexpr(std::forward_iterator<It>){
				vals.reserve(static_cast<size_type>(std::distance(first, last)));
			}
			for(; first != last; ++first){
				vals.push_back(*first);
			}
			std::sort(vals.begin(), vals.end(), comp_);
			vals.erase(std::unique(vals.begin(), vals.end(),
				[&](const value_type& a, const value_type& b){
					return !comp_(a, b) && !comp_(b, a);
				}), vals.end());
			build_from_sorted_unique(vals.begin(), vals.end());
		}

void rebalance(){
			if(alive_ < 2){ return; }
			std::vector<value_type> vals;
			vals.reserve(alive_);
			inorder([&](const value_type& v){ vals.push_back(v); }); //inorder sorts by cmp_		
			build_from_sorted_unique(vals.begin(), vals.end());
		}

[[nodiscard]] constexpr index_type find_index(const value_type& key) const noexcept{
			return find_with_parent(key).second;
		}

[[nodiscard]] constexpr bool contains(const value_type& key) const noexcept{
			return find_index(key) != npos;
		}

// returns pointer to value or nullptr 
		[[nodiscard]] inline constexpr const value_type* find(const value_type& key) const noexcept{
			index_type idx = find_index(key);
			return get_ptr(idx);
		}

[[nodiscard]] inline constexpr const value_type* get_ptr(index_type i) const noexcept{
			if(is_valid(i) && i < nodes_.size() && nodes_[i].has_value()){
				return &value_of(i);
			}
			return nullptr;
		}

// erase by key - returns true if erased
		constexpr bool erase(const value_type& key){
			auto [parent, cur] = find_with_parent(key);
			if(cur == npos){
				return false;
			}
			erase_at(parent, cur);
			return true;
		}

// traversals: inorder, preorder, postorder. Callback recieves const T&
		template<class F>
		constexpr void inorder(F&& f) const{
			std::vector<index_type> stack;
			stack.reserve(traversal_stack_reserve);
			index_type index = root_;
			while(is_valid(index) || !stack.empty()){
				while(is_valid(index)){
					stack.push_back(index);
					index = left_of(index);
				}
				index = stack.back();
				stack.pop_back();
				f(value_of(index));
				index = right_of(index);
			}
		}

template<class F>
		constexpr void preorder(F&& f) const{
			if(!is_valid(root_)) return;
			std::vector<index_type> stack;
			stack.reserve(traversal_stack_reserve);
			stack.push_back(root_);
			while(!stack.empty()){
				index_type index = stack.back();
				stack.pop_back();
				f(value_of(index));
				const node& n = get(index);
				if(is_valid(n.right)){
					stack.push_back(n.right);
				}
				if(is_valid(n.left)){
					stack.push_back(n.left);
				}
			}
		}

template<class F>
		constexpr void postorder(F&& f) const{
			if(!is_valid(root_)) return;
			std::vector<index_type> stack1, stack2;
			stack1.reserve(traversal_stack_reserve);
			stack2.reserve(traversal_stack_reserve);
			stack1.push_back(root_);
			while(!stack1.empty()){
				index_type index = stack1.back();
				stack1.pop_back();
				stack2.push_back(index);
				const node& n = get(index);
				if(is_valid(n.left)){
					stack1.push_back(n.left);
				}
				if(is_valid(n.right)){
					stack1.push_back(n.right);
				}
			}
			while(!stack2.empty()){
				index_type index = stack2.back();
				stack2.pop_back();
				f(value_of(index));
			}
		}

inline constexpr const_inorder_iterator begin_inorder() const{ return const_inorder_iterator(this, false); }
		inline constexpr const_inorder_iterator end_inorder()   const{ return const_inorder_iterator(this, true); }
		inline constexpr auto begin() const{ return begin_inorder(); }
		inline constexpr auto end() const{ return end_inorder(); }

private:
		struct node final{
			value_type value;
			index_type left = npos;
			index_type right = npos;
			constexpr explicit node(const value_type& v)  noexcept(std::is_nothrow_copy_constructible_v<value_type>) : value(v){}
			constexpr explicit node(value_type&& v)  noexcept(std::is_nothrow_move_constructible_v<value_type>) : value(std::move(v)){}
			template<class... Args>
			constexpr explicit node(std::in_place_t, Args&&... args)  noexcept(std::is_nothrow_constructible_v<value_type, Args...>) : value(std::forward<Args>(args)...){}
		};
		static constexpr size_type traversal_stack_reserve = 16; // Typical traversal depth (balanced trees rarely exceed log2(N). Just a perf hint, does not affect correctness.
		index_type root_ = npos;
		size_type alive_ = 0;
		std::vector<std::optional<node>> nodes_;
		std::vector<index_type> free_;
		[[no_unique_address]] Compare comp_{};

template<class V>
		constexpr index_type make_node(V&& v){
			if(!free_.empty()){ //can we re-use a free slot?
				index_type idx = free_.back();
				try{ // try construct before popping
					nodes_[idx].emplace(std::forward<V>(v));
					free_.pop_back();
					++alive_;
					return idx;
				} catch(...){
					// leave free_ unchanged and rethrow
					throw;
				}
			}
			// no free slots available, let's append (grow)
			index_type idx = static_cast<index_type>(nodes_.size());
			if(nodes_.size() == size_type(std::numeric_limits<index_type>::max())){
				throw std::length_error("flat::bst index overflow!");
			}
			nodes_.emplace_back(node(std::forward<V>(v))); // may throw, but no state updated yet
			++alive_;
			return idx;
		}

constexpr void tombstone(index_type idx){
			assert(is_valid(idx) && idx < nodes_.size() && nodes_[idx].has_value());
			nodes_[idx].reset();
			free_.push_back(idx);
			--alive_;
		}

constexpr node& get(index_type idx) noexcept{
			assert(is_valid(idx) && idx < nodes_.size() && nodes_[idx].has_value());
			return *nodes_[idx];
		}
		constexpr const node& get(index_type idx) const noexcept{
			assert(is_valid(idx) && idx < nodes_.size() && nodes_[idx].has_value());
			return *nodes_[idx];
		}
		
		// find_with_parent is a performance optimization for erase()
		// it returns both the matching node and its parent in one traversal.
		constexpr std::pair<index_type, index_type> find_with_parent(const value_type& key) const
			noexcept(noexcept(std::declval<const Compare&>()(std::declval<const T&>(), std::declval<const T&>()))) 
		{
			index_type parent = npos;
			index_type cur = root_;
			while(is_valid(cur)){
				const node& n = get(cur);
				if(comp_(key, n.value)){
					parent = cur;
					cur = n.left;
				} else if(comp_(n.value, key)){
					parent = cur;
					cur = n.right;
				} else{
					return {parent, cur}; // equal
				}
			}
			return {npos, npos};
		}

// link parent's child pointer to new child
		constexpr void relink_child(index_type parent, index_type old_child, index_type new_child){
			if(parent == npos){
				root_ = new_child;
				return;
			}
			node& p = get(parent);
			if(p.left == old_child){
				p.left = new_child;
			} else if(p.right == old_child){
				p.right = new_child;
			} else{
				assert(false && "parent does not point to old_child");
			}
		}

// erase at specific index, given its parent
		constexpr void erase_at(index_type parent, index_type cur){
			node& n = get(cur);
			// Case 1: 0 children
			if(!is_valid(n.left) && !is_valid(n.right)){
				relink_child(parent, cur, npos);
				tombstone(cur);
				return;
			}
			// Case 2: 1 child
			if(!is_valid(n.left) || !is_valid(n.right)){
				index_type child = is_valid(n.left) ? n.left : n.right;
				relink_child(parent, cur, child);
				tombstone(cur);
				return;
			}
			// Case 3: 2 children: replace value with inorder successor, then delete successor
			// Find leftmost in right subtree
			index_type succ_parent = cur;
			index_type succ = n.right;
			while(is_valid(left_of(succ))){
				succ_parent = succ;
				succ = left_of(succ);
			}
			n.value = std::move(value_of(succ));
			// remove successor node (which has at most one child on the right)
			index_type succ_right = right_of(succ);
			relink_child(succ_parent, succ, succ_right);
			tombstone(succ);
		}

template<class It>
		void build_from_sorted_unique_into_empty(It first, It last){
			assert(empty() && "Tree must be empty to use build_from_sorted_unique_into_empty");
			const size_type n = static_cast<size_type>(std::distance(first, last));
			if(n == 0){ root_ = npos; return; }
			nodes_.reserve(n);

auto build = [&](auto&& self, It lo, It hi) -> index_type{
				if(lo == hi) return npos;
				It mid = lo + (std::distance(lo, hi) / 2);
				index_type me = make_node(*mid);       // can throw, but *this* is still a valid empty-or-partial tree
				node& m = get(me);
				m.left = self(self, lo, mid);
				m.right = self(self, std::next(mid), hi);
				return me;
				};
			root_ = build(build, first, last);
		}

// unique-key insert helpers
		template<class V>
		constexpr std::pair<index_type, bool> insert_impl(V&& v){
			if(!is_valid(root_)){
				root_ = make_node(std::forward<V>(v));
				return {root_, true};
			}
			index_type parent = npos;
			index_type index = root_;
			while(is_valid(index)){
				parent = index;
				node& n = get(index);
				if(comp_(v, n.value)){
					index = n.left;
				} else if(comp_(n.value, v)){
					index = n.right;
				} else{ // equal - reject duplicate by default					
					return {index, false};
				}
			}
			index = make_node(std::forward<V>(v));
			node& p = get(parent);
			if(comp_(get(index).value, p.value)){
				p.left = index;
			} else{
				p.right = index;
			}
			return {index, true};
		}

template<class... Args>
		constexpr std::pair<index_type, bool> emplace_impl(Args&&... args){
			if(!is_valid(root_)){
				root_ = make_node(node(std::in_place, std::forward<Args>(args)...));
				return {root_, true};
			}
			// two-pass: descend with a temporary key constructed for comparisons,
			// then construct in place at leaf. To avoid extra T, we construct once,
			// then move into slot. That is fine for most Ts.
			value_type temp(std::forward<Args>(args)...);
			return insert_impl(std::move(temp));
		}
	};

template<class T, class Compare, class IndexT>
	void swap(bst<T, Compare, IndexT>& a, bst<T, Compare, IndexT>& b)
		noexcept(noexcept(a.swap(b))){
		a.swap(b);
	}
} //namespace flat

using flat::bst;

template<class T>
static std::vector<T> inorder_dump(const bst<T>& t){
	std::vector<T> out;
	t.inorder([&](const T& v){ out.push_back(v); });
	return out;
}

template<class T>
static std::vector<T> preorder_dump(const bst<T>& t){
	std::vector<T> out;
	t.preorder([&](const T& v){ out.push_back(v); });
	return out;
}

template<class T>
static std::vector<T> postorder_dump(const bst<T>& t){
	std::vector<T> out;
	t.postorder([&](const T& v){ out.push_back(v); });
	return out;
}

template<class T>
static void expect_equal_vec(const std::vector<T>& a, const std::vector<T>& b){
	assert(a == b);	
}

template<class T>
static void expect_strictly_increasing(const std::vector<T>& v){
	for(size_t i = 1; i < v.size(); ++i){
		assert(v[i - 1] < v[i]);
	}
}

// Test 1 - basic insert and size, inorder returns sorted unique values
static void test_basic_insert_and_inorder(){
	bst<int> t;	
	for(int v : {5, 2, 8, 1, 3, 7, 9}){
		auto [_, ins] = t.insert(v);
		assert(ins);
	}
	assert(t.size() == 7);
	auto in = inorder_dump(t);
	std::vector<int> expect = {1,2,3,5,7,8,9};
	expect_equal_vec(in, expect);
	expect_strictly_increasing(in);
}

// Test 2 - duplicates rejected, contains stays true, size does not grow
static void test_duplicate_insert(){
	bst<int> t;
	auto _ = t.insert(10);
	auto r1 = t.insert(10);
	assert(r1.second == false);
	assert(t.size() == 1);
	assert(t.contains(10));
	auto in = inorder_dump(t);
	expect_equal_vec(in, std::vector<int>{10});
}

// Test 3 - erase leaf node
static void test_erase_leaf(){
	bst<int> t;
	// Build a small tree where 1 will be a leaf
	for(int v : {5, 2, 8, 1, 3}){
		auto _ = t.insert(v);
	}
	assert(t.erase(1) == true);
	assert(t.size() == 4);
	assert(!t.contains(1));
	expect_equal_vec(inorder_dump(t), std::vector<int>{2, 3, 5, 8});
}

// Test 4 - erase node with one child
static void test_erase_one_child(){
	bst<int> t;
	// 5 root, 2 left, 1 left-left (so 2 has one child after removing 3)
	for(int v : {5, 2, 8, 1}){
		t.insert(v);
	}
	assert(t.erase(2) == true);  // 2 has one child (1)
	assert(t.size() == 3);
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 5, 8});
	assert(!t.contains(2));
}

// Test 5 - erase node with two children (successor splice)
static void test_erase_two_children(){
	bst<int> t;
	for(int v : {5, 2, 8, 1, 3, 7, 9}){
		t.insert(v);
	}
	// erase 2, which has children 1 and 3
	assert(t.erase(2));
	assert(!t.contains(2));
	assert(t.size() == 6);
	auto in = inorder_dump(t);
	std::vector<int> expect = {1,3,5,7,8,9};
	expect_equal_vec(in, expect);
	expect_strictly_increasing(in);
}

// Test 6 - find and find_index
static void test_find_and_find_index(){
	bst<int> t;
	const auto npos = bst<int>::npos;
	for(int v : {4, 2, 6, 1, 3, 5, 7}) t.insert(v);
	auto* p3 = t.find(3);
	assert(p3 && *p3 == 3);
	auto* p42 = t.find(42);
	assert(p42 == nullptr);
	auto i5 = t.find_index(5);
	assert(i5 != npos);
	auto i0 = t.find_index(0);
	assert(i0 == npos);
}

// Test 7 - traversal orders on a known tree
static void test_traversal_orders(){
	bst<int> t;
	// Shape:
	//        4
	//      2   6
	//     1 3 5 7
	for(int v : {4, 2, 6, 1, 3, 5, 7}){
		t.insert(v);
	}

expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 4, 5, 6, 7});
	expect_equal_vec(preorder_dump(t), std::vector<int>{4, 2, 1, 3, 6, 5, 7});
	expect_equal_vec(postorder_dump(t), std::vector<int>{1, 3, 2, 5, 7, 6, 4});
}

// Test 8 - const in-order iterator matches inorder traversal
static void test_inorder_iterator(){
	bst<int> t;
	for(int v : {10, 5, 15, 3, 7, 12, 18}){
		t.insert(v);
	}

std::vector<int> via_iter;
	for(auto it = t.begin_inorder(); it != t.end_inorder(); ++it){
		via_iter.push_back(*it);
	}
	expect_equal_vec(via_iter, inorder_dump(t));
	expect_strictly_increasing(via_iter);
}

// Test 9 - clear, empty, reserve have sane effects
static void test_clear_empty_reserve(){
	bst<int> t;
	t.reserve(100);
	assert(t.empty());
	for(int v : {3, 1, 4}){
		t.insert(v);
	}
	assert(!t.empty());
	t.clear();
	assert(t.size() == 0);
	assert(t.empty());
	// operations after clear still work
	t.insert(2);
	expect_equal_vec(inorder_dump(t), std::vector<int>{2});
}

// Test 10 - range constructor handles unsorted input with duplicates (sort+unique path)
static void test_ctor_range_unsorted_dupes(){
	std::vector<int> v = {5,2,8,1,3,7,9,3,5};
	bst<int> t(v.begin(), v.end()); // should sort+unique and then build balanced
	assert(t.size() == 7);
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 5, 7, 8, 9});
}

// Test 11 - range constructor fast path on already sorted unique input
static void test_ctor_range_sorted_unique_fastpath(){
	std::vector<int> v = {1,2,3,4,5,6,7};
	bst<int> t(v.begin(), v.end());
	assert(t.size() == 7);
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 4, 5, 6, 7});
	// The midpoint-balanced build should yield this preorder:
	expect_equal_vec(preorder_dump(t), std::vector<int>{4, 2, 1, 3, 6, 5, 7});
}

// Test 12 - initializer list constructor with duplicates
static void test_ilist_ctor_dupes(){
	bst<int> t{3,1,4,3,1};
	assert(t.size() == 3);
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 3, 4});
}

// Test 13 - bulk_insert basic and duplicate handling
static void test_bulk_insert(){
	bst<int> t;
	std::vector<int> a = {5,2,8,1,3,7,9};
	auto n1 = t.insert(a.begin(), a.end());
	assert(n1 == a.size());
	assert(t.size() == a.size());
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 5, 7, 8, 9});

// Insert some duplicates and one new element
	std::vector<int> b = {1,2,2,10};
	auto n2 = t.insert(b.begin(), b.end());
	assert(n2 == 1);                 // only 10 should be inserted
	assert(t.size() == a.size() + 1);
	assert(t.contains(10));
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 5, 7, 8, 9, 10});
}

// Test 14 - build_from_sorted_unique API constructs balanced tree
static void test_build_from_sorted_unique_api(){
	std::vector<int> v = {1,2,3,4,5,6,7};
	bst<int> t;
	t.build_from_sorted_unique(v.begin(), v.end());
	assert(t.size() == 7);
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 4, 5, 6, 7});
	expect_equal_vec(preorder_dump(t), std::vector<int>{4, 2, 1, 3, 6, 5, 7});
}

// Test 15 - build_from_range API sorts, uniques, and balances
static void test_build_from_range_api(){
	std::vector<int> v = {5,2,8,1,3,7,9,3,5};
	bst<int> t;
	t.build_from_range(v.begin(), v.end());
	assert(t.size() == 7);
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 5, 7, 8, 9});
}

// Test 16 - rebalance on a degenerate tree changes shape but preserves inorder and size
static void test_rebalance_changes_shape_preserves_order(){
	bst<int> t;
	// Ascending inserts form a degenerate chain
	for(int i = 1; i <= 7; ++i){
		t.insert(i);
	}
	// Preorder for a right-leaning chain of 1..7 is 1..7
	expect_equal_vec(preorder_dump(t), std::vector<int>{1, 2, 3, 4, 5, 6, 7});
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 4, 5, 6, 7});
	auto before_size = t.size();

t.rebalance();

// Inorder preserved and size unchanged
	assert(t.size() == before_size);
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 4, 5, 6, 7});
	// Balanced preorder should now be midpoint layout
	expect_equal_vec(preorder_dump(t), std::vector<int>{4, 2, 1, 3, 6, 5, 7});

// Basic ops still work after rebalance
	assert(t.contains(5));
	assert(!t.contains(42));
	t.erase(4);
	expect_equal_vec(inorder_dump(t), std::vector<int>{1, 2, 3, 5, 6, 7});
}

int main(){
	test_basic_insert_and_inorder();
	test_duplicate_insert();
	test_erase_leaf();
	test_erase_one_child();
	test_erase_two_children();
	test_find_and_find_index();
	test_traversal_orders();
	test_inorder_iterator();
	test_clear_empty_reserve();
	test_ctor_range_unsorted_dupes();
	test_ctor_range_sorted_unique_fastpath();
	test_ilist_ctor_dupes();
	test_bulk_insert();
	test_build_from_sorted_unique_api();
	test_build_from_range_api();
	test_rebalance_changes_shape_preserves_order();
	return 0;
}