I am receiving the following compile errors:

BinarySearchTree.cpp:3: error: expected constructor, destructor, or type conversion before â<â token
BinarySearchTree.cpp:9: error: expected initializer before â<â token
BinarySearchTree.cpp:15: error: expected initializer before â<â token
BinarySearchTree.cpp:21: error: expected initializer before â<â token

Looking at my implementation, I fail to see the errors. I wonder if overloading the methods is the problem or not. Here is the rest of my code:

#include <cstdlib>
#include <functional>

template <class T, class Key = T, class Compare = std::less<Key> >
class BinarySearchTree
		struct BinaryNode
			T data;
			Key key;
			BinaryNode *left;
			BinaryNode *right;
			BinaryNode() : {left = NULL; right = NULL;}
			BinaryNode(Key k, T i) : data(i), key(k) {left = NULL; right = NULL;}
			~BinaryNode() : {delete left; delete right;}

		BinaryNode *root;
		Compare compare;
		void InsertSorted(const T& data);
		void InsertSorted(const Key& key, const T& data);
		void InsertSortedR(const Key& key, const T& data, BinaryNode*& node);

#include "BinarySearchTree.cpp"

template <class T, class Key, class Compare>
BinarySearchTree<T, Key, Compare>::BinarySearchTree() 
	root = NULL;

template <class T, class Key, class Compare>
void BinarySearchTree<T, Key, Compare>::InsertSorted(const T& item)
	InsertSorted(item, item);

template <class T, class Key, class Compare>
void BinarySearchTree<T, Key, Compare>::InsertSorted(const Key& key, const T& item)
	InsertSortedR(key, item, root);

template <class T, class Key, class Compare>
void BinarySearchTree<T, Key, Compare>::InsertSortedR(const Key& key, const T& item, BinaryNode*& node)
	// Base case: Reached end of list, or found sorted position
	if (node == NULL || compare(key, node->key))
		// Create new list node
		BinaryNode *new_node = new BinaryNode(key, item);
		//new_node->next = node;
		// Update linked list
		node = new_node;
		if (root == NULL) // if list was empty, update tail
			root = new_node;
	// Recursive case:
		InsertSortedR(key, item, node->right);

If anyone could please help me with this error it would be greatly appreciated. Thanks in advance.

8 Years
Discussion Span
Last Post by DLightman

You can put the BinaryNode struct outside of the class and make the class look a little more cleaner.

Why are you including the .cpp file, it's not a header?

Shouldn't the destructor test if the pointers are NULL first?


First off I am going to deal with the minor errors. The the major problem.

Number of minor errors:

(A) Only constructors take the ":" assignment . Error in line 18 in
destructor. It should read ~BinaryNode() {delete left; delete right;} (B) Maybe delete line Compare compare . Use it as a direct functor if (node == NULL || Compare()(key, node->key)) Major:

This code is unlikely to behave as expected. If you put say in keys
3,5,1 then when it inserts a new node, it does no re-attach the
existing items to the tree. (as well as not working, this is a memory leak)

Additionally, I feel that you are being let down by your compiler. It is not reporting useful error messages. It really helps to have another compiler sometime (e.g. gcc) [likewise if you use gcc most of the time, something like Portland or IBM etc].

Finally, it is strange to include the .cpp file in the .h file. That is because you want to use the header without including all the code. If you need a template instance, then sometimes it needs to be done
but not all the time.

I look forward to the next installment :)


So the problem was part (A). Removed the colons and the code works. It might not be perfect, but it is functional. I included the cpp in the h file due to laziness. I used this class previously so there was not much to change. I've tried using Microsoft based compilers, but they have issues compiling my code where gcc finds no faults. I need to look into other compilers. Thanks for the help everyone!

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.