Binary Search Tree in C

Question

I have implemented a BST from scratch. My aim is to draft better code and understand some pitfalls which I may have overlooked.

It includes the following functionalities:

1. Insert a new item.
2. Find the Depth of a node, given the level of root is 0
3. Find the number of nodes in the subtree of a given node.
4. While removing the node, replace it with its inorder successor.

Ok, currently I am testing my code with various test cases I can come up with. One such test case and the proposed output is pasted here :

Test Case showing Input and Proposed Output

#include<stdio.h>
#include<stdlib.h>
int lastLabel = 0;
int lDepth = 0;
int rDepth = 0;
struct node
{
 int data;
 int label;
 struct node* parent;
 struct node* rightChild;
 struct node* leftChild;
};
struct node* createNode(int d)
{
 struct node* newN = (struct node*)malloc(sizeof(struct node));
 newN->data = d;
 newN->leftChild = '0円';
 newN->rightChild = '0円';
 newN->parent = '0円';
 lastLabel++;
 newN->label = lastLabel;
 return newN;
}
struct Queue
{
 int front,rear;
 int size;
 struct node** array;
};
typedef struct tree
{
 struct node* root;
 int size;
}BinaryTree;
////////Binary Tree Helper Functions//////////////////////
BinaryTree* createTree()
{
 BinaryTree* t = (BinaryTree*)malloc(sizeof(BinaryTree));
 t->root = '0円';
 t->size = 0;
 return t;
}
int size(BinaryTree *t)
{
 return t->size;
}
struct node* root(BinaryTree *t)
{
 return t->root;
}
struct node* parent(struct node* n)
{
 return n->parent;
}
int isInternal(struct node *n)
{
 return n->leftChild != '0円' || n->rightChild != '0円';
}
int isExternal(struct node *n)
{
 return !isInternal(n);
}
int isRoot(struct node* n)
{
 return n->parent == '0円';
}
int hasBothChild(struct node* temp) 
{
 if((temp!= '0円') && (temp->leftChild != '0円') && (temp->rightChild != '0円')) return 1;
}
////////Binary Tree Helper Functions//////////////////////
//Helper function to find the number of nodes of a particular subTree
int maxDepth(struct node* stree)
{
 if(stree == '0円') return 0;
 else 
 {
 lDepth = maxDepth(stree->leftChild);
 rDepth = maxDepth(stree->rightChild);
 if(lDepth > rDepth) return (lDepth + 1);
 else return (rDepth + 1);
 }
} 
int depthQuery(struct node* root,int key)
{
 struct node *temp_node = root; 
 while(temp_node != '0円')
 {
 if(temp_node->data == key)
 {
 return maxDepth(temp_node);
 }
 else if(key < temp_node->data && temp_node->leftChild != '0円')
 {
 temp_node = temp_node->leftChild;
 }
 else if(key > temp_node->data && temp_node->rightChild != '0円')
 {
 temp_node = temp_node->rightChild;
 }
 else
 {
 return 0; 
 }
 } 
 }
//sizeFind Helper to return the subtree. Cannot Live without sizeQuery
int sizeFind(struct node* stree)
{
 if(stree == '0円') return 0;
 else return(sizeFind(stree->leftChild) + 1 + sizeFind(stree->rightChild));
} 
//Helper function to find the particular nodes given the node's key
int sizeQuery(struct node* root,int key)
{
 struct node *temp_node = root; 
 while(temp_node != '0円')
 {
 if(temp_node->data == key)
 {
 return sizeFind(temp_node);
 }
 else if(key < temp_node->data && temp_node->leftChild != '0円')
 {
 temp_node = temp_node->leftChild;
 }
 else if(key > temp_node->data && temp_node->rightChild != '0円')
 {
 temp_node = temp_node->rightChild;
 }
 else
 {
 return -1; 
 }
 }
}
//insert data in the pre-existing Complete Binary Tree
struct node* insert(struct node* root,int data)
{
 if(root == '0円')
 {
 struct node* temp = createNode(data);
 root = temp;
 }
 else if(data <= root->data)
 {
 if(root->leftChild != '0円')
 {
 insert(root->leftChild,data);
 }
 else
 {
 struct node* temp = createNode(data);
 temp->parent = root;
 root->leftChild = temp;
 }
 }
 else
 {
 if(root->rightChild != '0円') insert(root->rightChild,data);
 else
 {
 struct node* temp = createNode(data);
 temp->parent = root;
 root->rightChild = temp;
 }
 }
 return root;
}
//perform InOrder Traversal 
void postOrder(struct node* root)
{
 if(root == '0円') return;
 if(isInternal(root)) postOrder(root->leftChild);
 if(isInternal(root)) postOrder(root->rightChild);
 printf("%d ", root->data);
}
struct node* minValue(struct node* node)
{
 struct node* currentNode = node;
 while(currentNode->leftChild != NULL)
 {
 currentNode = currentNode->leftChild;
 }
 return (currentNode);
}
struct node* inOrderSuccessor(struct node* root,struct node *n)
{
 if(n->rightChild != NULL) return minValue(n->rightChild);
 struct node* successor = NULL;
 int flagLR;
 struct node* succ = n->parent;
 while(succ != NULL && n == succ->rightChild)
 {
 n = succ;
 succ = succ->parent;
 }
 successor = succ; 
 return successor;
}
//The helper function will remove the node containing the Key(multiple instances possible), then it would replace that node with the Last Node
struct node* Delete(struct node* root,int key,int size)
{
 struct node *temp_node = root;
 while(temp_node)
 {
 if(temp_node->data == key)
 {
 //Find its inorder successor which is succ
 struct node* succ = inOrderSuccessor(root,temp_node);
 temp_node->data = succ->data;
 //Let the successor be removed from the BST, four ways
 //But first find if succ is the left or Right Child of its parent
 //*****************************************************************//
 int flagLR;
 if(succ->parent->leftChild == succ) flagLR = 0; //0 for LEFT CHILD
 else flagLR = 1; //1 for RIGHT CHILD
 //*****************************************************************//
 //Case 1 : succ is an External Node
 if(isExternal(succ) && succ->parent != '0円') 
 {
 if(succ->parent->leftChild == succ) succ->parent->leftChild = '0円';
 else succ->parent->rightChild = '0円';
 free(succ);
 } 
 //Case 2 : succ is an Internal Node with two children
 else if((hasBothChild(succ) == 1))
 {
 succ->parent->leftChild = succ->leftChild;
 succ->parent->rightChild = succ->rightChild; 
 succ->leftChild->parent = succ->parent;
 succ->rightChild->parent = succ->parent;
 } 
 //Case 3 : succ is the leftChild of the parent
 else if(succ->leftChild != '0円' )
 {
 succ->leftChild->parent = succ->parent;
 if(flagLR == 0)
 {
 succ->parent->leftChild = succ->leftChild;
 }
 else
 {
 succ->parent->rightChild = succ->leftChild;
 }
 }
 //Case 4 : succ is the rightChild of the parent
 else
 {
 succ->rightChild->parent = succ->parent;
 if(flagLR == 0)
 {
 succ->parent->rightChild = succ->rightChild;
 }
 else
 {
 succ->parent->rightChild = succ->rightChild;
 }
 }
 return root; 
 } 
 else if(key < temp_node->data && temp_node->leftChild != '0円')
 {
 temp_node = temp_node->leftChild;
 }
 else if(key > temp_node->data && temp_node->rightChild != '0円')
 {
 temp_node = temp_node->rightChild;
 }
 else
 {
 return '0円'; 
 } 
 }
} 
int main()
{
 int num_items;
 int key;
 int num_Ops;
 char op;
 int op_key;
 int ctr;
 int qcount;
 int i;
 int stree_ctr;
 scanf("%d",&num_items); 
 struct node* root = '0円';
 for(ctr = 0; ctr < num_items; ctr++)
 {
 scanf("%d",&key);
 root = insert(root,key);
 }
 postOrder(root);
 printf("\n");
 scanf("%d",&num_Ops);
 for(i = 0; i < num_Ops ; i++)
 { 
 while((op = getchar())== '\n');
 scanf("%d",&op_key);
 if(op == 'i') 
 {
 root = insert(root,op_key);
 postOrder(root);
 printf("\n");
 }
 else if(op == 'q')
 { 
 lDepth = 0;
 rDepth = 0;
 qcount = depthQuery(root,op_key);
 printf("%d\n",qcount);
 } 
 else if(op == 's')
 {
 stree_ctr = sizeQuery(root,op_key);
 printf("%d\n",stree_ctr);
 }
 else if(op == 'r')
 {
 root = Delete(root,op_key,lastLabel);
 postOrder(root);
 printf("\n");
 }
 }
 return 0;
}

• Heslacher: I have rolled back the last edit. Please see what you may and may not do after receiving answers .
• envy_intelligence: @Hesalcher, but the answer cannot be accepted from here as the issue is yet to be resolved. Any alternative apart from opening a new question. As it is, another question I had posted was not answered. This is decelerating my progress.
• Heslacher: What issue ? Your code should working aka running without exception and producing the expected result. If this is not the case, then your question is off topic. And you didn't just add the isPresent() method but you also changed the code in question which is against the rules on code review. If you need to add code because of missing context, so do it and write a note about it too but you should put it in a separate code block.
• envy_intelligence: @Heslacher,sorry was not aware of these rules.

Answer 1

I haven't finished the last function delete(). My remarks are mostly cosmetic stuff:

• use NULL for null pointers
• isExternal() would be best named isLeaf()
• use a bool type for functions that returns true/false values like isXXX() hasYYY(). See SO answer.
• hasBothChild() (should it be hasBothChildren()?) does not return a value for second branch of if. It could be simplified by just returning the result of the boolean condition.
• in maxDepth(), why are rDepth and lDepth global? they can be declared locally to the function.
• consistency of return value between depthQuery() and sizeQuery() when the key is not found. Both 0 or both -1 ?
• clean up inOrderSuccessor(): root param is not used, successor and flagLR are not used.

• envy_intelligence: I think delete() and inOrderSuccessor() SEGFAULT for the case which has been added.
• envy_intelligence: Can you please try this out and let me know? I am wasting hours on this!!
• T.Gounelle: What do you expect after inserting -1? As I see it (-2) will have a right child with (-1). That's right?
• envy_intelligence: Inserting an entry already present in the BST is not allowed. So I use the isPresent function to check it and let it pass.
• T.Gounelle: isPresent() is not in the listing. Reading more carefully the inOrderSuccessor() function, I think there is a problem when you call it on the node that holds the biggest value. In this case it should return NULL, since there is no successor. Right now if you have a simple tree with 2 values (root=1, rightchild=2) and you call inOrderSuccessor('2'), you will get '1' instead of NULL. With that, you need to check for a NULL successor in Delete() before calling succ->parent, etc.