macOS C++ Binary Search Tree Problem

[steelphantom]

I'm trying to write a simple binary search tree in C++, and I'm getting hung up on the insert function, more specifically, where the program checks to see if my node is NULL. The if statement evaluates as false and nothing gets inserted. Could anyone give me a hint as to what I'm doing wrong? Thanks!

Here's my code:

#include <iostream>

using namespace std;

struct Node
{
	int value;
	Node *left;
	Node *right;
};

void visit(Node *ptr)
{
	if (ptr->left == NULL)
		visit(ptr->left);
		
	cout << ptr->value;
	
	if (ptr->right == NULL)
		visit(ptr->right);
}

void insert(int data, Node *ptr)
{
	if (ptr == NULL)
	{
		ptr = new Node;
		ptr->value = data;
		ptr->left = NULL;
		ptr->right = NULL;
	}
	else if (data < ptr->value)
		insert(data, ptr->left);
	else if (data > ptr->value)
		insert(data, ptr->right);
}

int main()
{
	Node *myTree = new Node;
	insert (5, myTree);
	cout << myTree->value << endl;
	return 0;
}

 

[saltyzoo]

You haven't initialized a root node. So the line "else if (data < ptr->value)" is going to puke on you as value in the ptr node is null.

 

[fimac]

I'm trying to write a simple binary search tree in C++, and I'm getting hung up on the insert function, ...

Given test data of { 5, 3, 8, 4, 7 } do you expect to see this?

      5
     / \
    /   \
   3     8
  /\     /\
 /  \   /  \
    4   7

If so, then this is a good use-case for pointer-to-pointers This allows us to simplify the insert() function: it simply allocates a new node, or recurses.

#include <iostream>

using namespace std;

struct Node
{
  int   value;
  Node *left;
  Node *right;
};

static void
visit(Node const *ptr)
{
  if (NULL != ptr)
    {
      visit(ptr->left);
      cout << ptr->value << endl;
      visit(ptr->right);
    }
}

static void
insert(int value, Node **pp)
{
  if (NULL == *pp)
    {
      *pp          = new Node;
      (*pp)->value = value;
      (*pp)->left  = NULL;
      (*pp)->right = NULL;
    }
  else if (value < (*pp)->value)
    {
      insert(value, &(*pp)->left);
    }
  else if (value > (*pp)->value)
    {
      insert(value, &(*pp)->right);
    }
  else
    {
      // ignore duplicates
    }
}

int
main(void)
{
  Node *root = NULL;

  insert(5, &root);
  insert(3, &root);
  insert(8, &root);
  insert(7, &root);
  insert(4, &root);

  visit(root);

  return 0;
}

 

[lazydog]

I'm trying to write a simple binary search tree in C++, …

Hi
I think I can see a few problems with your code:-

Your Node struct does not have any constructors. You really need to initialise the left and right poitners to null. Somthing like this…

struct Node
{
	int value;
	Node *left;
	Node *right;

};

 

[lazydog]

I'm trying to write a simple binary search tree in C++, …

Hi
I think I can see a few problems with your code:-

Your Node struct does not have any constructors. You really need to initialise the left and right pointers to null. Something like this…

struct Node
{
	int value;
	Node *left;
	Node *right;

     Node() : left( 0L ), right( 0L ) {}

};

Also in visit() change the if condition to:-

if (ptr->left != NULL)

Since you're using C++ why not make visit() and insert() member functions of Node?

b e n

 

[fimac]

You really need to initialise the left and right pointers to null.

Yes. "new" is not guaranteed this automatically for us.

Good point about this being C code -- IMHO that's ok; I sometimes use C++ as simply a better C

 

[saltyzoo]

"new" does this automatically for us.

No, in fact, it doesn't. That is the problem here.

 

[Lyle]

"new" does this automatically for us.

Good point about this being C code -- IMHO that's ok; I sometimes use C++ as simply a better C

No, in fact, it doesn't. That is the problem here.

saltyzoo is right; you can't count on those members being initialized automatically. Even if one C++ compiler happens to do this for you, you shouldn't count on that behavior to portable to other C++ implementations.

By the way, I think Java does guarantee that those members will be initialized to zero (for the value) or null (for the pointers), which can lead to some confusion if you have to switch back and forth between those languages.

 

[steelphantom]

OK, does this take care of the initialization step?

int main()
{
	Node *myTree = new Node;
	myTree->left = myTree->right = NULL;
	insert (5, myTree);
	cout << myTree->value << endl;
	return 0;
}

It still doesn't work correctly, so I'm obviously doing something wrong.

Thanks lazydog for pointing out my stupid error in the visit() function.

fimac, your solution works, but I think pointers to pointers are even more confusing for me. I'd like to get this to work without using them.

Also, this will eventually be implemented into a class, but I want to get the basics working first. Thanks everyone for your help! Pointers have become a real stumbling block for me.

 

[Lyle]

OK, does this take care of the initialization step?

I'd also initialize myTree->value to zero. As your code is currently written, its value is undefined.

Once you've done that, the initial call to insert() should drop into the third if-branch, because ptr is not NULL and the data (which is 5) is greater than the current node's value (which is zero). So that will trigger a call to insert(5, NULL).

On this call to insert(), ptr is NULL and so you'll construct a new Node and initialize its value to 5. Unfortunately, you haven't provided any way for the parent node (myTree) to link to this. That is, at some point you want to assign this newly constructed node to the "right" pointer for myTree.

Hang in there. Pointers are hard to get the hang of.

 

[madmoose]

Here's how I'd solve it. The separate Tree-class helps to manage the initialization problems and cleanup.

#include <iostream>

class Node
{
	friend class Tree;

	int value;
	Node *left;
	Node *right;

	Node(int value) : value(value), left(0), right(0)
	{
	}

	~Node()
	{
		delete left;
		delete right;
	}

	void insert(int newValue);
	void visit();
};

void Node::insert(int newValue)
{
	// This could also be written non-recursively

	if (newValue < value)
	{
		if (left)
			left->insert(newValue);
		else
			left = new Node(newValue);
	}
	else if (newValue > value)
	{
		if (right)
			right->insert(newValue);
		else
			right = new Node(newValue);
	}
	// else value already exists
}

void Node::visit()
{
	if (left)
		left->visit();

	std::cout << value;

	if (right)
		right->visit();
}

class Tree
{
	Node *root;

public:
	Tree() : root(0)
	{
	}

	~Tree()
	{
		delete root;
	}
	
	void insert(int newValue);
	void visit();
};

void Tree::insert(int newValue)
{
	if (root)
		root->insert(newValue);
	else
		root = new Node(newValue);
}

void Tree::visit()
{
	if (root)
	{
		root->visit();
		std::cout << std::endl;
	}
}

int main()
{
	Tree t;
	const int data[] = { 5, 3, 8, 7, 4 };

	for (unsigned int i = 0; i < sizeof(data)/sizeof(data[0]); ++i)
		t.insert(data[i]);

	t.visit();
}

 

[lazydog]

OK, does this take care of the initialization step?

int main()
{
	Node *myTree = new Node;
	myTree->left = myTree->right = NULL;
	insert (5, myTree);
	cout << myTree->value << endl;
	return 0;
}

It still doesn't work correctly, so I'm obviously doing something wrong.

Your code doesn't actually set the value of myTree.value. myTree is acting as the root node of your tree and so you should be initialising it's value. Your original insert() function needs fixing too. The pointer you pass should be a pointer of the parent node. That way when insert() creates a new node the parent can be set to point to it, either by setting the parent's left or right values. Here's how I see your insert function working:-

void insert( int value, Node* parent )
{
    if ( value == parent->value )
     //
     // Nothing to do.
     // 
     return ;

  if ( value < parent->value )
    if ( parent->left == NULL )
      parent->left = create_new_node( value ) ;
   else
      insert( value, parent->left ) ;
  else
     same for right!
}

Node* create_new_node( int value )
{
   Node* node = new Node() ;
   node->left = node->right = NULL ;
   node->value = value ;

  return node ;
}

Since you're not using constructors I've added a create node function. This initialises the node and set's its value.

b e n