create a binary search tree and add a node, traverse inoder, breadth first search, find fourth smallest

const int MaxN = 50;

class node;

class queue
{
public:
queue() {begin = end = -1;}
void enque(node* n)
{
if(empty())
begin = 0;
elem[++end] = n;
}

node* deque()
{
node* t;
if(begin == -1)
return 0;

if(begin == end)
{
t=elem[begin];
begin = end = -1;
}
else
t=elem[begin++];
return t;
}

int empty() { return (begin == -1)? 1: 0;}

private:
node* elem[MaxN];
int begin;
int end;
};

class node
{
public:
int n;
node* l;
node* r;
};

class bst
{
public:
bst() {r= NULL;}
void addnode(int n);
void traverseinorder() {traverseinorder(r);}
void bfs() {bfs(r); }
void fourthsmallest() {fourthsmallest(r);}
private:
void addnode(node* p, int n);
void traverseinorder(node* r);
void bfs(node* r);
void fourthsmallest(node* p);
node* r; //root
};

void bst::addnode(int n)
{
if(!r)
{
r = new node();
r->n = n;
r->l = NULL;
r->r = NULL;
return;
}
addnode(r, n);
}

void bst::addnode(node* p, int n)
{
if(n < p->n)
{
if(p->l)
addnode(p->l, n);
else
{
p->l = new node();
p->l->n = n;
p->l->l = NULL;
p->l->r = NULL;
return;
}
}
else
{
if(p->r)
addnode(p->r, n);
else
{
p->r = new node();
p->r->n = n;
p->r->l = NULL;
p->r->r = NULL;
return;
}
}
}

void bst::traverseinorder(node* p)
{
if(!p)
return;
traverseinorder(p->l);
cout << p->n << " ";
traverseinorder(p->r);
}

void bst::fourthsmallest(node* p)
{
static int count=0;
if(!p)
return;
fourthsmallest(p->l);
count++;
if(count == 4)
cout << "4th smallest = " << p->n < fourthsmallest(p->r);

}

void bst::bfs(node* p)
{
if(!p)
return;

queue t;
t.enque(p);

node dummy;
dummy.n = -1;

cout << "\n\n breadth first traverse\n";
t.enque(&dummy);

while(!t.empty())
{
node* k = t.deque();
while(k && k->n == -1)
{
cout << endl;
k = t.deque();
}

cout << k->n << " ";
if(k->l)
t.enque(k->l);
if(k->r)
t.enque(k->r);

t.enque(&dummy);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
bst tr;
cout << "enter numbers to create a BST (-1 as end of input)\n";
while(1)
{
int n;
cin >> n;
if(n < 0)
break;
tr.addnode(n);
}

cout << "inorder: ";
tr.traverseinorder();

tr.bfs();

tr.fourthsmallest();
return 0;
}