Preorder Binary Search Tree Insertion

Question

A painfully stupid question that I am almost too ashamed to ask. I have been searching for the past 4 hours, tested different algorithms, tried quite a few on paper and still can't get it to work.

I will spare you the details of the project implementation, but the basic question is: "How do you handle inserting nodes in a Pre-Order Binary Tree.

By Pre-Order BST, I mean that all nodes should be inserted in such a way, that traversing the tree using pre-order traversal (e.g for printing) should print the nodes in ascending order.

All I need is a simple algorithm. I tried a simple insertion algorithm given here (on stackoverflow, but it seems to be incorrect (also tried it on paper));.

The nodes are basically like:

typedef struct testNode{
    int key;
    struct testNode *leftChild;
    struct testNode *rightChild;
}NODE;

Insertion data is just a list of unique integers. I create a node with the int as key and then should add the node to the tree. I have the root node, which starts off as a NULL pointer.

Sorry if anything isn't clear.

Thanks for the help!

EDIT: Based on the algorithm provided below, this is what I came up with:

void insert(NODE **tree,int key){
if(*tree){
    if ((*tree)->key >= key){
        //Insert before this .....
        NODE *temp = createNode(key);
        temp->lc = (*tree);
        (*tree) = temp;

    }
    else if(!(*tree)->rc){
        //Right Child doesn't exist ....
        insert(&(*tree)->lc,key);
    }
    else if((*tree)->rc->key < key){
        //Right child exists and is smaller than spread ... insert left ...
        insert(&(*tree)->lc,key);
    }
    else{
        //Right child exists and is greater than spread ... insert right ...
        insert(&(*tree)->rc,key);
    }
    //If the code as progressed to this point, insertion must have occured, 
            //and the code returns ......   
} else {
    //the **tree pointer points to NULL. Insert here ....
    SPREADNODE *temp = createSpreadNode(spread);
    //temp->lc = (*tree);
    (*tree) = temp;
}
}

Answer 1

Think about the definition of a pre-ordered BST: The root node is the smallest element, and its two children or also pre-ordered trees such that the root of the right subtree is larger than any value in the left subtree.

So, one algorithm that would work would be:

1. If the new node is smaller than the root, make it the new root and point to the existing tree as one of the two child nodes.
2. If the new node is larger than the root, but smaller than the root of the right subtree, recursively insert it into the left subtree.
3. Otherwise, recursively insert it into the right subtree.

This isn't likely to produce a very balanced tree, but it should work. I can think of at least one other simple alternative, and there are no doubt ways to make things more balanced that I leave as an exercise to the reader ;-)