Because it was quick, it isn't perfect. Search will have trouble finding all nodes if there are more than 1 with the same value, and I will leave delete for you to implement.

Also, this code was not well tested, you should check the accuracy of the results.

In addition to your requirements, you may also wish to implement a

`Balance()`

method to balance the tree, otherwise in extreme circumstance it can end up as a linked list with a bigger memory footprint.#include <stdio.h> #include <malloc.h> #include <stdlib.h> //I don't know if Turbo C has NULL defined #ifndef NULL #define NULL 0 #endif typedef struct tagBSTNode { int nValue; //This could be a struct or whatever other data type you are using as the nodes tagBSTNode *pLeft; //The left child node for elements that are less than this element tagBSTNode *pRight; //The right child node for elements that are greater than or equal to this node } BSTNode; BSTNode *CreateNode(int nValue) { //The parameter here would be whatever data type the node is representing BSTNode *pNode = (BSTNode *)malloc(sizeof(BSTNode)); if (pNode == NULL) { puts("Out of memory."); exit(-1); } pNode->nValue = nValue; pNode->pLeft = NULL; pNode->pRight = NULL; return pNode; } void DestroyNode(BSTNode *pNode) { if (pNode != NULL) { free(pNode); } } void DestroyTree(BSTNode *pHead) { if (pHead->pLeft != NULL) { DestroyTree(pHead->pLeft); } if (pHead->pRight != NULL) { DestroyTree(pHead->pRight); } DestroyNode(pHead); } //This function compares 2 BSTNodes and returns their relationship in terms of sorted order: // <0 if pNode1 < pNode2 // =0 if pNode1 == pNode2 // >0 if pNode1 > pNode2 int CompareNodes(BSTNode *pNode1, BSTNode *pNode2) { if (pNode1->nValue < pNode2->nValue) { return -1; } else if (pNode1->nValue > pNode2->nValue) { return 1; } else { return 0; } } //This function compares a BSTNode and an int and returns the relationship in terms of sorted order: // <0 if pNode > nValue // =0 if pNode == nValue // >0 if pNode < nValue int CompareNode(BSTNode *pNode, int nValue) { if (pNode->nValue > nValue) { return -1; } else if (pNode->nValue < nValue) { return 1; } else { return 0; } } //Returns the new head of (sub)tree. In most cases this will be the same value as pHead. BSTNode *InsertNode(BSTNode *pHead, BSTNode *pNew) { if (pHead == NULL) { //The tree is empty. return pNew; //This is now the head element in the tree } if (CompareNodes(pNew, pHead) < 0) { //pNew needs to go to the left if (pHead->pLeft == NULL) { //There are no child nodes on the left. Set it and return the head. pHead->pLeft = pNew; } else { pHead->pLeft = InsertNode(pHead->pLeft, pNew); //Recurse through the tree untill we find an empty child node } return pHead; //Return the head element } else { //pNew needs to go to the right //This could also be that pNew == pHead. It is up to you which side it goes, I chose right (greater than) if (pHead->pRight == NULL) { //There are no child nodes on the right. Set it and return the head. pHead->pRight = pNew; } else { pHead->pRight = InsertNode(pHead->pRight, pNew); //Recurse through the tree untill we find an empty child node } return pHead; //Return the head element } } void PrintTreePreOrder(BSTNode *pHead) { //Iterates the tree in pre-order and prints each element //Hopefully you can see how to do pre-order and post-order printf("%d ", pHead->nValue); if (pHead->pLeft != NULL) { PrintTreePreOrder(pHead->pLeft); } if (pHead->pRight != NULL) { PrintTreePreOrder(pHead->pRight); } } void PrintTreeInOrder(BSTNode *pHead) { //Iterates the tree in order and prints each element if (pHead->pLeft != NULL) { PrintTreeInOrder(pHead->pLeft); } printf("%d ", pHead->nValue); if (pHead->pRight != NULL) { PrintTreeInOrder(pHead->pRight); } } void PrintTreePostOrder(BSTNode *pHead) { //Iterates the tree in post-order and prints each element if (pHead->pLeft != NULL) { PrintTreePostOrder(pHead->pLeft); } if (pHead->pRight != NULL) { PrintTreePostOrder(pHead->pRight); } printf("%d ", pHead->nValue); } BSTNode *SearchTree(BSTNode *pHead, int nValue) { if (pHead == NULL) { return NULL; //Element not found } int nCmp = CompareNode(pHead, nValue); if (nCmp == 0) { return pHead; //This is the element we are looking for } else if (nCmp < 0) { return SearchTree(pHead->pLeft, nValue); } else { //if (nCmp > 0) return SearchTree(pHead->pRight, nValue); } } int main() { BSTNode *pBST = NULL; //This will build a sample tree from the following values int nSampleValues[] = { 5, 1, 8, 0, 2, 3 }; int nSearchValues[] = { 3, 1, 7 }; int nValue; for (nValue = 0; nValue < sizeof(nSampleValues) / sizeof(nSampleValues[0]); ++nValue) { pBST = InsertNode(pBST, CreateNode(nSampleValues[nValue])); } printf(" Pre-order: "); PrintTreePreOrder(pBST); printf("\n"); printf(" In-order: "); PrintTreeInOrder(pBST); printf("\n"); printf("Post-order: "); PrintTreePostOrder(pBST); printf("\n"); for (nValue = 0; nValue < sizeof(nSearchValues) / sizeof(nSearchValues[0]); ++nValue) { printf("Searching for %d: ", nSearchValues[nValue]); if (SearchTree(pBST, nSearchValues[nValue]) == NULL) { printf("Not Found\n"); } else { printf("Found\n"); } } //Cleanup the memory used DestroyTree(pBST); return 0; }