Binary Search Tree

bst.h

#pragma once

#include <list>

template<class T>
class BST {
public:
	struct Node {
		T value;
		Node *lhs, *rhs, *parent;
		bool operator<(Node &a) { return value < a.value; }
		bool operator==(Node &a) { return value == a.value; }
	};
public:
	explicit BST() { Node n; data.push_back(n); }
	~BST() {}
	Node *root() { return &data.front(); }
	Node *add(T child, Node *parent=nullptr, bool right=true) {
		Node n; n.value = child; n.lhs = n.rhs = nullptr;
		data.push_back(n);
		auto *ptr = &data.back();
		if(parent) { (right?parent->rhs:parent->lhs)=ptr; ptr->parent = parent; }
		else {
			auto *p = root();
			while(true) {
				if(ptr->value < p->value) {
					if(p->rhs == nullptr) { p->rhs = ptr; break; }
					p = p->rhs;
				} else {
					if(p->lhs == nullptr) { p->lhs = ptr; break; }
					p = p->lhs;
				}
			}
		}
		return ptr;
	}
	Node *search(T q) {
		auto *ptr = root();
		while(ptr!=nullptr) {
			if(ptr->value==q) return ptr;
			ptr = (q < ptr->value ? ptr->rhs : ptr->lhs);
		}
		return ptr;
	}
private:
	std::list<Node> data;
};