// bstree.cpp
#include "bstree.h"

template<class type>
void insert_rec(node<type> *&ptr, type someitem)  // dereference the thing that ptr points to
{
	if (ptr == 0) ptr = new node<type>(someitem,0,0);
	else if (ptr->item > someitem) insert_rec(ptr->lptr,someitem);
	else insert_rec(ptr->rptr,someitem);
}

template<class type>
void bstree<type>::insert(type someitem)
{
	insert_rec(root_ptr,someitem);
}

template<class type>
Bool search_rec(node<type> *&ptr, type someitem)
{
	// We want to traverse the tree to search for duplicates
	// Return true if a duplicate is found; false otherwise
	Bool found = False;

	if (ptr==0) return False;
	if (ptr->item==someitem) return True;
	if (ptr->lptr!=0) found = search_rec(ptr->lptr,someitem);
	if (ptr->rptr!=0 && !found) found = search_rec(ptr->rptr,someitem);
	return found;
}

// Why do we have these functions outside ... something to do with root_ptr?


template<class type>
Bool 	bstree<type>::search(type someitem)
{
	return search_rec(root_ptr,someitem);
}

// ---------------------------------------------------------

template<class type>
int 	height_rec(node<type> *&ptr)
{
	int lh = 0;
	int rh = 0;

	if (ptr->is_leaf()) return 1;
	else
	{
		if (ptr->lptr!=0) lh=height_rec(ptr->lptr);
		if (ptr->rptr!=0) rh=height_rec(ptr->rptr);

		if (lh>rh) return (lh+1);
		else return (rh+1);
	}
}

template<class type>
int 	bstree<type>::height()
{
	return height_rec(root_ptr);
}

template<class type>
void rangeSearch_rec(node<type> *&ptr,type lo, type hi)
{
	if ((hi>=ptr->item)&&(ptr->item>=lo)) cout<< ptr->item <<endl;
	if (ptr->lptr!=0) rangeSearch_rec(ptr->lptr,lo,hi);
	if (ptr->rptr!=0) rangeSearch_rec(ptr->rptr,lo,hi);
}

template<class type>
void bstree<type>::rangeSearch(type lo, type hi)
{
	rangeSearch_rec(root_ptr,lo,hi);
}