Different output depending on whether or not I print the return value

Question

So I have a simple snippet of C++ code which is SUPPOSED to insert a node into a binary search tree. It returns true if the value is successfully inserted and false if the value is already in the tree.

struct Node {
  int data;
  Node* parent = nullptr;
  Node* left = nullptr;
  Node* right = nullptr;
};

bool insert(Node& root, int data) {
  if (data > (root.data)) {
    if ((root.right) == nullptr) {
      Node newNode = {data, &root};
      root.right = &newNode;
      return true;
    } else {
      return insert(*root.right, data);
    }
  }
  else if (data < (root.data)) {
    if ((root.left) == nullptr) {
      Node newNode = {data, &root};
      root.left = &newNode;
      return true;
    } else {
      return insert(*root.left, data);
    }
  }
  else {
    return false; // if both values are equal 
  }
}

When testing my function I noticed something peculiar. When I don't print the function's return value, it gives the right answer (20):

  Node root = {50};
  insert(root, 20);
  cout << (root.left->data) << endl;

However, when I do print the return value, it gives the incorrect result (0):

  Node root = {50};
  cout << insert(root, 20) << endl;
  cout << (root.left->data) << endl;

I cannot possibly fathom why this happens, but my best bet is because of some weird memory hijinks, perhaps not allocating new memory for the struct? I come from Python where memory management is handled automatically so I'm still getting used to situations like this.

Answer 1

You invoke undefined behaviour right there:

  Node newNode = {data, &root};
  root.right = &newNode;

This stores, in your tree, the address of a stack variable. As soon as the function returns, it's not legal anymore to dereference this Node's children. From there, anything could happen.

You probably want something like:

  Node* newNode = new Node;
  newNode.data = data;
  newNode.root = root;
  ...
  root.right = newNode;

Edit: Remember that whenever you put a new in code, you need a matching delete. To avoid this hassle, the modern approach is to use unique_ptr. You should look into that. In your case, since you keep back pointers to the root, you'll need either shared_ptr and/or weak_ptr.