0

The below is my code for inserting elements into a Binary Search Tree. The insert function has two parameters, value which is the number to be inserted into the tree and root, which is the root of tree.

My root->getLeft() and root->getRight() both return a BinaryNode*, which is why I'm thinking its returning this error:

BST.cpp: In function ‘void insert(int, BinaryNode*&)’:
BST.cpp:72:34: error: invalid initialization of non-const reference of type ‘BinaryNode*&’ from an rvalue of type ‘BinaryNode*’

void insert(int value, BinaryNode*& root) {
        cout << "Looping" << endl;
      if(root == NULL) {
        BinaryNode* node = new BinaryNode(value);
        root = node;
        cout << "finalized" << endl;
        cout << "Root value: " << root->getValue() << endl;
      }
      else if(value < root->getValue()) {
          insert(value, root->getLeft());
          cout << "went to left" << endl;
      }
      else if(value >= root->getValue()) {
          insert(value, root->getRight());
          cout << "went to right" << endl;
      }
    }

How would I modify root->getLeft() so that the right value (*&) is passed in?

Additionally, what exactly does *& mean? I've been testing only passing in BinaryNode* root and the changes to root never seem to take effect, e.g. root forgets its value outside of insert and in the past only *& has seemed to work to change the actual value of the original.

Thanks!

Jonas
  • 6,915
  • 8
  • 35
  • 53
kevin shen
  • 61
  • 6
  • 1
    "Additionally, what exactly does *& mean?" that's a reference to a pointer. If that makes no sense to you, it's time to [crack a good book on C++](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) and read the first few chapters. – user4581301 Apr 18 '17 at 06:27
  • Just a guess that `root->getLeft()` and `root->getRight()` return a `BinaryNode*`, which is a copy of some other pointer. When you update the copy, the original pointer is *not* changed. The compiler tries to tell you that, by mentioning that you cannot bind a temporary (an rvalue) to a non-const reference. – Bo Persson Apr 18 '17 at 08:12

1 Answers1

1

This is a rule in C++ language: You can not bind a r-value to l-value reference

Consider this example:

// Foo return a r-value
some_type foo();

// binding r-value to l-value reference is not valid
some_type& var = foo();

In this example we are returning a temporary object from foo that will be destroyed when the assignment expressing return, and so we will have a dangled reference. This is why you can't bind a r-value to a l-value reference.

In your code root->getLeft() return a r-value of type BinaryNode* and then you are binding it to BinaryNode*& which is a l-value reference.

Even if you can bypass that error, your code has problem: root->getLeft() return a pointer which is temporary variable, then in your insert function you are changing a temporary pointer via it's BinaryNode*& root parameter. You should return a reference to node pointers (BinaryNode*&) from getLeft() and getRight().

MRB
  • 3,752
  • 4
  • 30
  • 44