Unit testing a binarysearchtree

lets say you have this binary search tree (BST). See code below. Properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.

• The right subtree of a node contains only nodes with keys greater than the node’s key.

• Both the left and right subtrees must also be binary search trees.

How would you unit test it? You can't access the nodes and can't verify the structure. You can't test the Insert function separately.

1) You can create an inherited test class from BST and declare extra methods to be able to test. Is this common?

2) Implement the BST differently. Have a Tree class. This class can access child nodes etc. and implements basic tree functionality. Inherit BST from Tree. Test BST with the help of methods provided by Tree.

3) Your opinion?

Thank you.

template <typename ValueType>
class BinarySearchTree
{
public:

    BinarySearchTree() : m_count(0), m_root(nullptr) {}
    void Insert(const ValueType& elementToInsert);
    bool Remove(const ValueType& elementToRemove);
    bool Contains(const ValueType& elementToFind);
    bool IsEmpty() const;
    size_t Count() const;
    ValueType Max() const;
    ValueType Min() const;
    int Delimiter() const;
    void PrintToFile(std::ofstream& outFile);
    void BuildFromFile(std::ifstream& inFile);
    ~BinarySearchTree() { delete m_root; }
    // TODO: copy ctr, copy assignment operator, move ctr

private:

    struct Node
    {
        Node(const ValueType& value) : value(value), parent(nullptr), left(nullptr), right(nullptr) {}
        ~Node() { delete left; delete right; }
        // TODO: copy ctr, copy assignment operator, move ctr

        ValueType value;
        Node* parent;
        Node* left;
        Node* right;
    };

    Node* m_root;
    int m_count;
};