Bartek Wichowski Bartek Wichowski - 1 month ago 9
C++ Question

pointer to struct as function argument - why its value is not updated?

I try to build binary tree starting from empty root pointer, but tree do not appear. However when firstly I add any leaf to tree, everything works fine. My question is, what is wrong in insert function that root pointer is not updated.

#include<iostream>
using namespace std ;
struct BTree
{
int value;
BTree *left;
BTree *right;
};

BTree* newLeaf(int _value)
{
BTree *p;
p = new BTree;
p -> value = _value;
p -> left = nullptr;
p -> right = nullptr;
return p;
}

void insert(BTree *root, int _value)
{
if (root == nullptr)
{
root = newLeaf(_value);
/*why after enteting here root is still nullptr*/
cout << "entered" << endl;
return;
}

if (root -> value == _value)
{
return;
}
else if (root -> value > _value)
{
if (root -> left == nullptr)
{
root -> left = newLeaf(_value);
return;
}
else
{
insert(root -> left, _value);
}
}
else
{
if (root -> right == nullptr)
{
root -> right = newLeaf(_value);
return;
}
else
{
insert(root -> right, _value);
}
}
}

void print(BTree *root, int i)
{
if (root == nullptr)
{
return;
}

cout << "Level :" << i << " " <<
root -> value << endl;

print(root -> left, i + 1);
print(root -> right, i + 1);

}

int main(){
/*1. that works properly */
/*BTree *root = newLeaf(10);*/

/*2. that does not work */
BTree *root = nullptr;
insert(root, 10);

/*rest of code*/
insert(root,5);
insert(root,1);
insert(root,3);
insert(root,12);
insert(root,11);
insert(root,13);

print(root, 0);
return 0 ;
}

Answer
root = newLeaf(_value);

Since root is passed to insert() by value, this accomplishes nothing useful. This sets the root parameter to insert(), but the root object in main() remains unchanged. It's a different object. That's what "passing by value" means.

You need to pass the pointer by reference:

void insert(BTree *&root, int _value)

Incidentally, having done that it should no longer be necessary to check if the left or the right child is null, before making the recursive call.