#include <iostream>
#include <cstdlib>
using namespace std;

struct node {
	int value;
	node * left;
	node * right;
	bool deleted;
};

void insert(node *parent, int value);
void preorderTraverse(node *ptr);

void insert(node *parent, int value)
{

	if (!parent->value)
	{
		parent->value = value;
		return;
	}

	/*
	node *child;
	if (parent->value > value) //Child needs to be a reference not a copy
		child = parent->left; //This compiles (a copy)
	else
		child = &parent->right; //This doesn't (attempt at pointer)

	if (child == NULL)
	{
		child = new node();
		child->value = value;
		return;
	}

	insert(child, value);
	*/

	if (parent->value > value)
	{
		if (parent->left == NULL)
		{
			parent->left = new node();
			parent->left->value = value;
			return;
		}
		insert(parent->left, value);
	} else
	{
		if (parent->right == NULL)
		{
			parent->right = new node();
			parent->right->value = value;
			return;
		}
		insert(parent->right, value);
	}
};

void preorderTraverse(node *ptr)
{
	if (ptr != NULL)
	{
		printf("\nValue = %d", ptr->value);
		preorderTraverse(ptr->left);
		preorderTraverse(ptr->right);
	}
};

int main (int argc, char * const argv[]) {

	node * tree = new node();

	for (int x = 0; x < 100; x++)
		insert(tree, rand());

	preorderTraverse(tree);

    return 0;
}