Difficulty inserting nodes to binary search tree using templates and template inheritance

Question

What I am dealing with is I have created 3 template classes. I am trying to make a library for binary trees though I have limited knowledge of C++. I have implemented binary trees in C using structs but this time I wanted to take advantage of the object oriented programming C++ offers so I created classes for the node, the binary tree and the binary search tree.

I feel more comfortable showing all the code in case there is something else wrong that I didn't notice. So here it is. (Note: C++11 in use)

node_class.h

template <typename key_type, typename value_type>
class node_class {
public:
    node_class(key_type key, value_type value) {
        SetKey(key);
        SetValue(value);
        SetLeft(nullptr);
        SetRight(nullptr);
    }
    void SetKey(key_type key) {
        this->key = key;
    }
    void SetValue(value_type value) {
        this->value = value;
    }
    void SetLeft(node_class <key_type, value_type> *left) {
        this->left = left;
    }
    void SetRight(node_class <key_type, value_type> *right) {
        this->right = right;
    }
    key_type GetKey() {
        return this->key;
    }
    value_type GetValue() {
        return this->value;
    }
    node_class <key_type, value_type> *GetLeft() {
        return this->left;
    }
    node_class <key_type, value_type> *GetRight() {
        return this->right;
    }
private:
    key_type key;
    value_type value;
    node_class <key_type, value_type> *left;
    node_class <key_type, value_type> *right;
};

binary_tree_class.h

template <typename key_type, typename value_type>
class binary_tree_class {
public:
    binary_tree_class() {
        SetRoot(nullptr);
    }
    // ...
protected:
    void SetRoot(node_class <key_type, value_type> *root) {
        this->root = root;
    }
    node_class <key_type, value_type> *GetRoot() {
        return this->root;
    }
private:
    node_class <key_type, value_type> *root;
    // ...
};

binary_search_tree_class.h

template <typename key_type, typename value_type>
class binary_search_tree_class : public binary_tree_class <key_type, value_type> {
public:
    binary_search_tree_class() {

    }
    void Insert(key_type key, value_type value) {
        Insert(key, value, this->GetRoot());
    }
    void Insert(key_type key, value_type value, node_class <key_type, value_type> *node) {
        if (node == nullptr) {
            node = new node_class <key_type, value_type> (key, value);
        }
        if (key > node->GetKey()) {
            Insert(key, value, node->GetRight());
        } else if (key < node->GetKey()) {
            Insert(key, value, node->GetLeft());
        }
    }
    // ...
};

As far as the Insert function is conserned, I read that I have to pass the node parameter by reference to pointer in order for the changes to the tree to take place (Correct me if I am wrong). That being said I have to change the function protorype from this

void Insert(key_type key, value_type value, node_class <key_type, value_type> *node)

into this

void Insert(key_type key, value_type value, node_class <key_type, value_type> *&node)

After I did that I was completely unable to figure out what is wrong so I am still stuck with the following error from g++

In file included from main.cpp:1:0:
binary_search_tree_class.h: In instantiation of ‘void binary_search_tree_class<key_type, value_type>::Insert(key_type, value_type) [with key_type = int; value_type = int]’:
main.cpp:5:31:   required from here
binary_search_tree_class.h:11:9: error: invalid initialization of non-const reference of type ‘node_class<int, int>*&’ from an rvalue of type ‘node_class<int, int>*’
   Insert(key, value, this->GetRoot());
         ^
binary_search_tree_class.h:13:7: note:   initializing argument 3 of ‘void binary_search_tree_class<key_type, value_type>::Insert(key_type, value_type, node_class<key_type, value_type>*&) [with key_type = int; value_type = int]’
  void Insert(key_type key, value_type value, node_class <key_type, value_type> *&node) {

In the files above I couldn't write the include directives because the # symbol was causing problems with the indentation but I think you get it.

Possible duplicate of [How come a non-const reference cannot bind to a temporary object?](https://stackoverflow.com/questions/1565600/how-come-a-non-const-reference-cannot-bind-to-a-temporary-object) — 463035818_is_not_an_ai, Sep 04 '17 at 21:19
your `GetRoot` returns the pointer by value, ie if you call `this->GetRoot()` you get a temporary that is then passed to `Insert`, even this would work it would not do what you want, because it would only change the value of that temporary pointer, not to the `root` member — 463035818_is_not_an_ai, Sep 04 '17 at 21:20
Great effort! OP. Once you've gotten past the compiler error, I **strongly** suggest you send this code to http://codereview.stackexchange.com/ because there's a ton of things in your code that could use some improvements. Once you do, you may share the link in the comments here. — WhiZTiM, Sep 04 '17 at 21:22
you could make a `GetRootRef` that returns a reference to the pointer, or directly make the `root` protected — 463035818_is_not_an_ai, Sep 04 '17 at 21:22
@WhiZTiM :) Thanks for your kind words. I hope I solve this out. Right now I am trying out some things tobi303 said. — , Sep 04 '17 at 21:27
`the # symbol was causing problems with the indentation` - the code formatting works fine, but it didn't work because code blocks (1) need a blank line before them, and (2) need four spaces on the line before them. Try again? — halfer, Sep 05 '17 at 08:08

BiagioF · Accepted Answer · 2017-09-04T21:54:47.133

Issue

The issue starts from the method:

node_class<>* binary_search_tree<>::GetRoot();

It returns the copy pointer of the variable member root.

In other words, when you invoke the method GetRoot() you obtain the address location of the root node, and potentially save that address into another pointer variable.

Just to give you an idea. Let us suppose there is the root node somewhere in the memory:

 0x01 [...]
 0x02 [RootNode]
 0x03 [...]

Your binary tree will keep the address of the root node and store it in a pointer (which is a variable anyway).

The layout memory will be something like:

0x01 [...]
0x02 [RootNode]
0x03 [...]
0x04 [binary_tree::root = 0x02]

Let us suppose we invoke in order to take the root address: GetRoot() it will actually return the address of RootNode and not a reference to the member variable binary_tree:root which points to the RootNode.

So when you invoke GetRoot() with:

void foo() {
  auto p = binary_tree.GetRoot();
}

The layout memory will be something like:

0x01 [...]
0x02 [RootNode]
0x03 [...]
0x04 [binary_tree::root = 0x02]
0x05 [...]
0x06 [p = 0x2]

As you can see in the scheme, p is a copy of root (variable member), but they are, indeed, two different pointers which actually point the same location memory.

So if you pass p as reference to a function which modifies it, then p will be modified but not the member variable ::root.

The scheme and code is quite schematic, but I hope they will help you to understand the situation. GetNode() acts like copying the member variables and not returning a reference to it.

Your compile error comes from the fact that you are not actually saving the return copied address into another pointer, but directly passing it as argument. Therefore a temporary expression is created and passed to method Insert. However a temporary expression cannot be identified by a location in the memory and so you cannot take a reference from it, that's why your compiler says to cannot take a reference from a temporary value.

How to fix it?

There are several methods to approach that problem.

My opinion you can change your class design: just make the member variable protected in order to be accessed. In that way you can obtain the "real" pointer and not a copying address value.

Simple suggestions

This may be personal, but I think that the notation with pointer reference is quite unreadable. If your function (or method) needs to modify the address of a pointer, just use: void foo(node_class**) (pointer to pointer).
Adding _class to each name class is quite redundant and make the code more verbose. A class name should be just node.

First of all thanks for the effort you put to explain the problem to me. As far as the class names are concerned I was using the European Space Agency Standard for C/C++. I understand the problem now but I tried the pointer to pointer solution but I couldn't get the function call correct. Then I proceeded to the second solution you provided so I got rid of the GetRoot() function and changed the root pointer to protected but it didn't work either :/ — , Sep 04 '17 at 22:59
@xorz57 You should have `*root` as protected member variable and delete `GetRoot`. In derived method `Insert` you should pass `root` as third argument (the argument still has to be `node_class*&` because you need to change the address of the pointer). — BiagioF, Sep 05 '17 at 09:09

Difficulty inserting nodes to binary search tree using templates and template inheritance

1 Answers1

Issue

How to fix it?

Simple suggestions