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

Question

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.

• Robert Harvey: 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?
• yomag1234: @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
• trent: 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.
• Jerry Jeremiah: You could pass the tree class into the constructor and use composition. If you want inheritance, what about CRTP ?
• Doc Brown: Your question is hard to understand because you missed to give an example showing the potential differences between different variants of Derived.

Answer 1

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();
 }
};

• yomag1234: Thank you, that's exactly what I meant.
• trent: @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?"
• yomag1234: @trentcl Thanks, I will look it up for sure.

Answer 2

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:

template <class Payload>
class BinaryTree
{
public:
 BinaryTree(std::vector<int> &vec);
 BinaryTree<Payload> *left;
 BinaryTree<Payload> *right;
 std::vector<int> dataVector;
 Payload *payload;
 //functions...
};

Alternatively, without using templates, Payload can be an abstract base class for different kind of base classes.

This will give you a clearer separation between the content of each node and the tree structure, allowing you to write more generalized code for the tree creation and individual code for specialized payload handling, or vice versa.

• yomag1234: First off, thank you for an extensive answer.The differences between the different derived classes are the functions for sorting the binary tree, but there are small differences in tree construction as you've speculated.That's one of the parts I've abstracted away using functions in BinaryTree, with specialized templates for the differences, but it's nice knowing template-less approach works just fine. Also I'm not sure what you mean by Payload, if it's the data held by the node, I only need the vector, and I'm not sure how it's superior to use polymorphism only to hold instance variables?
• Doc Brown: @yomag1234: if your different derived classes don't contain additional members, you don't need any payload. For this case, Robert Harvey's comment is correct, it makes probably no sense to use inheritance at all, just put the different tree constructions in some other class. And Kain0_0's answer then seems to be even more overdesigned than it already is.
• yomag1234: to clarify, now I have derived classes with instance variables and functions required for different tree construction, sorting etc. I should put those in a payload class, and add it to binary tree as a pointer, and also add two other nodes of the payload class? But the derived classes (or the payload) need to know about the other nodes for construction and other functions. I'm confused as to who composites what and what the contents of different classes should be.
• Doc Brown: @yomag1234: I think it is hard to tell what would be most suitable without seeing the actual code.
• yomag1234: I've added a concrete derived class to better explain my intent.