>doing a preorder traversal would output it in order
Preorder traversal or did you mean inorder traversal? Because most projects assume a binary search tree, and if a preorder traversal gave the values in order then it would violate the strict ordering of a binary search tree. As described, you want this tree:
1
2 9
3 6 10 13
4 5 7 8 11 12 14 15 Whereas a proper binary search tree that's complete would be more like this:
8
4 12
2 6 10 14
1 3 5 7 9 11 13 15 The latter is trivial to do, and I'll give you some quick code so that you can use it as an example for developing your own solution if it turns out that you really do want the fomer tree.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left, *right;
} *root = NULL;
struct node *insert ( struct node *root, int data )
{
if ( root == NULL ) {
root = malloc ( sizeof *root );
if ( root == NULL ) {
fprintf ( stderr, "Memory exhausted\n" );
exit ( EXIT_FAILURE );
}
root->data = data;
root->left = root->right = NULL;
}
else if ( data < root->data )
root->left = insert ( root->left, data );
else
root->right = insert ( root->right, data );
return root;
}
void traverse ( struct node *root )
{
if ( root != NULL ) {
traverse ( root->left );
printf ( "%d ", root->data );
traverse ( root->right );
}
}
void build_complete ( int l, int r )
{
if ( r >= l ) {
int m = ( l + r ) / 2;
root = insert ( root, m );
build_complete ( l, m - 1 );
build_complete ( m + 1, r );
}
}
int main ( void )
{
int n = ( 1U << 4 ) - 1;
build_complete ( 1, n );
traverse ( root );
return 0;
} As you can see, figuring out how many items are in a complete tree of level h is trivial. Simply take 2 to the power of h and subtract 1 from the result, this is the number of nodes you will need. Creating a proper binary search tree from there is simple with a divide and conquer technique.
Creating the type of tree that you want is not as obvious, but the solution will be similar in complexity. Keep that in mind when you try to work out your own implementation.