Can you define node pointers in a base binary tree class?

I've created two separate binary tree classes, with some shared functions/variables and some that are not shared. So I have tried to abstract away the similarities in a base BinaryTree class.

class BinaryTree{
public:
BinaryTree(std::vector<int> &vec);

BinaryTree *left;
BinaryTree *right;
std::vector<int> dataVector;
//functions...
}

The derived classes share the type of data with the base class (dataVector). But they require the creation of new nodes of their derived type.

class Derived : public BinaryTree{
public:
void function(){
left = new BinaryTree();
};

Obviously by creating a new BinaryTree, we lose the extended functionality of the Derived class, but if I were to declare left and right as Derived* inside the Derived class, I would defeat the whole purpose of abstraction in the first place.

How would I go about implementing this if it's even possible?

EDIT: one of the derived classes might implement quick sort

class QuickSort : public BinaryTree{
public:

//chooses whether to sort itself or the children nodes recursively
void sortVector(){
if(isSorting) partition(),
else if (left->isSorting || left->areNodesSorting) left->sortVector();
else if(right->isSorting || right->areNodesSorting) right->sortVector();
}

void partition(){ /* partition implementation */};

void setupNodes(){
/* choose where to split dataVector depending on the pivot, and initialize
the pointers - left = new QuickSort(chosenVector); etc*/ };

bool isSorting = true, isLeaf = true, areNodesInit = false, areNodesSorting =
false;

int pivotIndex, j = 0, i = -1;
int pivotValue;

}

There are obviously other helper functions. And I need step by step sorting, so I've put all the variables as instance variables - should they be part of Payload? Also as you can see some functions use recursion and need to know of all the different children nodes as well.

• I don't think inheritance applies here at all. You have the BinaryTree class which represents a node, and functions that operate on nodes. You can put those functions anywhere you want; inheritance is not required. Ask yourself: what IS A relationship are you modelling here? Mar 11 '21 at 20:18
• @RobertHarvey as I said, I already have multiple classes representing a node, BinaryTree is supposed to abstract away the similarities to avoid duplicate code. If there's a better way to achieve it, I'm all ears Mar 11 '21 at 21:09
• Since in the example it's not obvious why function can't apply to all BinaryTrees, I think it would make the question better if you show an example of what "extended functionality" you're trying to achieve and why it can't be done in a single (generic?) class. Mar 11 '21 at 21:34
• You could pass the tree class into the constructor and use composition. If you want inheritance, what about CRTP ? Mar 11 '21 at 21:44
• Your question is hard to understand because you missed to give an example showing the potential differences between different variants of Derived. Mar 13 '21 at 13:03

In C++, or a language that has suitable generics.

template <typename node>
class BinaryTree
{
public:
BinaryTree(std::vector<int> &vec);

node *left;
node *right;
std::vector<int> dataVector;
//functions...
};

class Derived : public BinaryTree<Derived>
{
public:
void function(){
left = new Derived();
}
};
• Thank you, that's exactly what I meant. Mar 12 '21 at 15:00
• @yomag1234 It was mentioned in the question comments, but this is popularly known as the curiously recurring template pattern (CRTP). It's worth knowing the name, so the next time it comes up you'll say "oh, that" instead of "curious what?" Mar 12 '21 at 20:21
• @trentcl Thanks, I will look it up for sure. Mar 13 '21 at 11:25

Kain0_0's answer contains a working solution, but at the same time it gives the wrong impression this recurring template pattern would be necessary to solve what you asked for.

What you literally asked for is much simpler to solve: just leave the BinaryTree as it is, and replace

`left = new BinaryTree();`

by

`left = new Derived();`

I assume the whole tree construction algorithm is part of Derived, and may be different in classes Derived1, Derived2, Derived3.

Your question is actually missing a clear description of what the differences between Derived1, Derived2, ... are. This could be the tree construction, but also the "payload" for each node of the binary tree. If that's the case, you may introduce such an attribute into the binary tree, and use the templating for this:

class BinaryTree
{
public:
BinaryTree(std::vector<int> &vec);

std::vector<int> dataVector;