BST array

I need some help brainstorming an algorithm for implementing a given array into a BST array.

This is what I am stuck with using:

My example array is "val[-1,4,2,1,3,6,5,7]" and I need to omit -1 and put the rest of the values correctly in a BST array "bst[4 2 6 1 3 5 7]". However, the bst array is first initialized to "bst[-1 -1 -1 -1 -1 -1 -1]". For some reason these arrays are global, too.

My function call can only have two parameters in the main function: addBST(1, val[i]);

This is what I'm thinking..

addBST(int root, int newNode)
function call one:
if val[root] == -1
bst[root-1] = val[root+1];

function call two:
if newNode < bst[root-1]
if (bst[(root-1)*2+1] == -1)
{ bst[(root-1)*2+1] = newNode }
else
addBST(bst[(root-1)*2+1], newNode)

This is what I have brainstormed so far. I would like some advice from experienced C programmers. Thanks in advance, friends.

Why don't you throw together a sample program and see how it works?


Quzah.

Those child position calculations appear to be a bit off.
You can notice from your sample array that children should be at parent*2+1 and parent*2+2.
Also, the parent is at (child-1)/2.

It looks kind of weird because root == 1. One of the requirements is that the root parameter is always passing "1". So it is actually bst[(1-1)*2+1] == bst[1]. I haven't compiled anything yet, but I think that is the best way to move to the next node still; albeit, I could still be quite wrong.

Well what you're got should work fine for getting to the left chld then.
I wonder if they're insisting on skipping index zero to make it "easier" or whether they just don't realise that it isn't actually any harder or less efficient not to skip the first element.
They'll probably just confuse some people into thining that arrays start at one.
Not sure how we can be of much more assistance without seeing how you're going with the code.

Touching back with the main rules:

The array val[8] = {-1,4,2,1,3,6,5,7} is initialized.
The array bst[] is initialized to -1.

Writing two functions for a BST and preOrder traversal with arrays, the rules of the game are the parameters for the call functions must be: (val[i] is using a loop)

Code:

 
addBST(0,val[i]);

preOrder(0);

I came up with some solutions, but they're the most intellectually devoid solutions I have ever come up with. I seem to have a mental road block before me. Does anyone have any problem solving solutions to make this code more efficient?

Also, any suggestions on how to alter the program if the call parameters for root had to be "1" instead of "0"? Thanks in advance, friends.

Code:

void addBST(int root,int newNode)
{
	
	if (newNode < 0)
	  {bst[root] = val[root+1]; return; }

	if (newNode == val[root+1])
	  {return;}
	
	if (newNode < bst[root])
	  {
	  if (bst[(root)*2+1] == -1)
	    { bst[(root)*2+1] = newNode; return;}
	  else
	    addBST(((root)*2+1), newNode);
	  }

	if (newNode > bst[root])
	  {
	  if (bst[(root)*2+2] == -1)
	    { bst[(root)*2+2] = newNode; return;}
	  else
	    addBST(((root)*2+2), newNode);
	  }

	  return;

}

void preOrder(int root)
{

if (bst[root])
	{
	if (bst[root] != -1)
		{
		printf(" %d ", bst[root]);	
		preOrder((root*2+1));
		preOrder((root*2+2));
		}
	 }


}