# Building a Binary Search Tree off sorted data

• 12-01-2003
BlackCitan
Building a Binary Search Tree off sorted data
The problem: My teacher provided an algorithim for building a BST off sorted data so that it wasn't a linear chain, but I must have missed something. The program must also be able to build a BST off unsorted data. The function I wrote for that works fine, but the function I can't write should look somewhat similar.

This function builds a new node, pretty straight-forward.
Code:

```Node *MakeNode (int lines, string entry) {     Node *newNode = malloc (sizeof(Node));     strcpy (newNode->entry, entry);     newNode->leftTree  = NULL;     newNode->rightTree = NULL;     newNode->lineNumbers = calloc (lines, sizeof(int));     newNode->count = 0;     return newNode; }```
This is the function that inserts nodes into the tree with unsorted data...
Code:

```Node *ReadTree1 (int flag, Node *root, Node *newNode)     if (root == NULL)     {         if (flag == 1)             newNode->entry[0] = toupper(newNode->entry[0]);         root = newNode;     }     else if (strcmp(newNode->entry, root->entry) < 0)         root->leftTree = ReadTree1 (flag, root->leftTree, newNode);     else         root->rightTree = ReadTree1 (flag, root->rightTree, newNode);     return root; }```
Now here's what I have for the sorted data code...
Code:

```Node *ReadTree2 (int flag, int size, Node *root, Node *newNode) {     if (size > 0)     {         if (flag == 1)             newNode->entry[0] = toupper(newNode->entry[0]);         root = newNode;     }     else         if (strcmp (newNode->entry, root->entry) < 0)             root->leftTree = ReadTree2 (flag, size/2, root->leftTree, newNode);         else             root->rightTree = ReadTree2 (flag, (size-1)/2, root->rightTree, newNode);     return root; }```
I hope my question makes sense. If not, I'll gladly post anything else necessary. The flag isn't part of the main problem, and size is the number of items in the tree.