My task is to create a complete binary tree. The only requirements are that it be a dynamic tree with nodes and pointers - I may use temporary arrays to help with the intial tree construction. Where I need help is with the insert(Node) method. Here's what I have so far:

void BinaryTree::insert(int data, TreeNode* subTreeRoot, const
TreeNode*& parent)
{
TreeNode temp;
temp = subTreeRoot;

if ( subTreeRoot == NULL ) {
subTreeRoot = new TreeNode(-1,NULL,NULL,temp);
}
else if ( subTreeRoot->left == NULL ) {
insert(data,subTreeRoot->leftLink,temp);
}
else if ( subTreeRoot->right == NULL ) {
insertNode (data,subTreeRoot->rightLink,temp);
}
else {
insert(data,subTreeRoot->leftLink,subTreeRoot->leftLink);
insert(data,subTreeRoot->rightLink,subTreeRoot->rightLink);
}
}

Each node has three links and one data field - leftLink,rightLink,parent, and data. The reason for the parent link is to help with another part of the project. Basically, the problem I have is inserting the nodes in the proper "complete binary tree" method. That is, how do I insert the nodes in such a manner that all leafs are at height n or n-1 of a n tall tree? I believe the code I have right now will simply insert nodes on the far most left side, which will not create a complete binary tree. The code correctly creates a tree with a root and two children, but I believe it falls apart after that. Also, how do I keep track of the parent so that I can store that into the parent link field? I'm not sure if my current method accomplishes that.

I am trying to use a recursive method to accomplish my task, but I may have to switch to using temporary arrays.

Any help is greatly appreciated. I will be working on this all day so please reply if you have any input at all.

Thanks.

I always thought this was a good help. Well the concept anyway. The rest is just programming semantics.

http://cslibrary.stanford.edu/110/BinaryTrees.html

I went ahead with the temporary array approach. Much more simplistic.