---
tags: codebook
---

{%hackmd theme-dark %}

# shortest bst

#include<iostream>

template<typename T>struct bst{bst():rt(0){}
	bst(const auto& v):rt(0){for(const T& i:v) insert(i);}
    struct nd{T k;nd*p[2];nd(const T& x):k(x){p[0]=p[1]=0;}}*rt;
    void is(const T&x,nd*&c){
        if(c){is(x,c->p[c->k<x]);}else c=new nd(x);
    }void insert(const T& x){is(x,rt);}
    void pt(auto& o,nd*c){if(!c){return;}
        pt(o,c->p[0]);o<<c->k<<' ';pt(o,c->p[1]);
    }void print(auto& o){pt(o,rt);o<<std::endl;}};

---

#include<iostream>

template<typename T> struct bst {
	bst(auto&& v = {}): r(0) {for (const T& i : v) inser(i);}
	struct n {T k; n*p[2]; n(const T& x): k(x) {p[0] = p[1] = 0;}} *r;
	void i(const T&x, n*&c) {
		if (c) i(x, c->p[c->k < x]); else c = new n(x);
	} void inser(const T& x) {i(x, r);}
	void pt(auto& o, n*c) {
		if (c) pt(o, c->p[0]), o << c->k << ' ', pt(o, c->p[1]);
	} void print(auto& o) {pt(o, r), o << std::endl;}};

#include<vector>
int main() {
	bst<int> tree(std::vector<int> {1, 5, 4, 3, 2});
	tree.print(std::cout);
	return 0;
}