binary search tree removal - stuck - HELP!!

[Tarique Jawed]

Alright I needed some help regarding a removal of a binary search
tree. Yes its for a class, and yes I have tried working on it on my
own, so no patronizing please. I have most of the code working, even
the removal, I just don't know how to keep track of the parent, so
that I can set its child to the child of the node to be removed.

IE - if I had
C
/ \
B D
/ /
A E
\
F

Hope the post doesnt take away the spaces.

And I wanted to remove E, then I would set the left of D to F (the
child of E).

Correct??

I'll post the following code which is specifically the remove function
first - followed by the rest of it.

And I wanted to remove D, then I would set the left of C to E (the
child of D).

Correct??

I'll post the following code which is specifically the remove function
first - followed by the rest of it.


Also the assignment spec is as follows

Write a C program in a single file that implements a binary search
tree of words in a dictionary. Your program should have a pointer
variable that references the root of the binary tree. Initially the
tree will be empty.

Your program should ask the user if he or she wants to insert a data
value, remove a data value or print the content of the tree. Use
integers to indicate which option the user wants (1 for insert, 2 for
remove, 3 for printing the inorder traversal of the tree, 4 for
printing the preorder traversal of the tree and 5 for exiting the
program).
If the user wants to insert a data value, the program should prompt
the user for the word to insert, and it should then insert the word
into the binary search tree at its proper position. If the word is
already in the tree, print an appropriate message.
If the user wants to remove a data value, the program should prompt
the user for the word to remove, and it should then try to locate the
word in the binary search tree, and if it is there, remove it from the
tree. Otherwise, display an appropriate message for the user. To
simply the assignment, you are not required to remove a node with two
children, so if the user wants to remove such a node, print an
appropriate message and ignore the entry.
You should implement the insert operation, remove operation, inorder
traversal and the preorder traversal as separate functions in your C
program.
NOTES:
1. All declarations (variable, type, define, etc.) before the main
program are global. Make sure you define the variables for your main
program within main (to make them local to main) and do NOT make all
variables global.

2. Although your code can be saved in separate files, but do not do
this for this assignment. Submit your program in a single file named
"dictionary.c".

3. Each word contains only letters and its maximum length is 15.
Following statement shows how you can define this maximum value:

#define WORD_SIZE 15

4. Since debugging in C will be significantly harder than in Java, you
may include debugging code in your program that can be "turned off"
when you don't need it anymore (instead of commenting it out or
erasing it). See HW4 for the idea.

5. You will need to use dynamic memory allocation for this assignment.
Whenever a node is removed from the tree, be sure to free its memory
allocation. Also, once the user exits the program, if there are nodes
still in the tree, these must be de-allocated as well!

Thanks in advance to anyone who can help me out - my background is
really more in java, and this is my first C project, but I figured
this is what I should really learn, if I ever want to be any good.
void removeNode(node **tree, char removeData[WORD_SIZE])
{
// Traverse Tree to find node to remove
// If Node has both children, dont remove throw error
// If not, remove node and bring up proper child.
int leftChild = 0; // 0 is false 1 is true
int rightChild = 0;
int bothChild = 0; // 0 is false and 1 is true
int compareValue = 0;

if ( ((*tree)->left) != NULL)
leftChild=1;
if ( ((*tree)->right) != NULL)
rightChild=1;
if ( (leftChild==1) && (rightChild==1) )
bothChild = 1;

if (*tree == NULL)
{
printf("\nEmpty Tree Nothing to Remove.\n");
return;
}
compareValue = strcmp(removeData, (*tree)->data);

// String is found and does not have two children
if ( (compareValue == 0) && (bothChild == 0) )
{
if (leftChild == 1)
{
printf("\nData Found, and it has a left Child.");
// Set the left of the parent to the
return;
}

if (rightChild == 1)
{
printf("\nData found, and it has a right child.\n");
return;
}
// Remove Current and Make right the current

else
{
printf("\nData found, and it has no children\n");
return;
}
// Remove Current Node

}

if ( (compareValue == 0) && (bothChild == 1) )
{
printf("\nNode found but has both children, cannot be removed.\n");
}

if ( (compareValue < 0) && (leftChild == 0) )
{
printf("\nData is not in left child of the tree.\n");
return;
}

if ( (compareValue > 0) && (rightChild == 0) )
{
printf("\nData is not in right child of the tree.\n");
return;
}
if ( (compareValue < 0) && (leftChild == 1) )
{
//Go Left while there is a left
printf("\nLeft going remove.\n");
removeNode( &(*tree)->left, removeData);
}

if ( (compareValue > 0) && (rightChild == 1) )
{
//Go right while there is a right
printf("\nRight going remove.\n");
removeNode( &(*tree)->right, removeData);

}
}


Finally all the code is here

I am wondering, am I approaching this incorrectly, in terms of the
algorithm.??

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define WORD_SIZE 15

struct node_type {
char data[WORD_SIZE];
struct node_type *left, *right;
};

typedef struct node_type node;
// Prototypes
void inorder(node *tree);
void preorder(node *tree);
void postorder(node *tree);
void insertNode(node **tree, node **insertData);
void removeNode(node **tree, char removeData[WORD_SIZE]);

// Left - Root - Right
void inorder(node *tree)
{
if (tree->left)
inorder(tree->left);
printf("%s ", tree->data);

if (tree->right)
inorder(tree->right);
}
// Root Left Right
void preorder(node *tree)
{
printf("%s ", tree->data);
if (tree->left)
preorder(tree->left);
if (tree->right)
preorder(tree->right);
}
// Left - Right - Root
void postorder(node *tree)
{
if (tree->left)
preorder(tree->left);
if (tree->right)
preorder(tree->right);
printf("%s ", tree->data);
}
void insertNode(node **tree, node **insertData)
{ // If the root is null put it there
// Otherwise keep going left until you should place data.
// Otherwise go right until you should place data.
if (*tree == NULL)
{
*tree = *insertData;
return;
}
else if ( (strcmp((*tree)->data, (*insertData)->data)) == 0)
{
printf("Same data, cannot overwrite.\n");
}
else if ( (strcmp((*tree)->data, (*insertData)->data)) > 0)
{
printf("Go Left\n");
insertNode(&(*tree)->left, insertData);
}

else if ( (strcmp((*tree)->data, (*insertData)->data)) < 0)
{
printf("Go Right\n");
insertNode( &(*tree)->right, insertData);
}

//printf("\nAfter insertion: %s\n", (*tree)->data);
}
void removeNode(node **tree, char removeData[WORD_SIZE])
{
// Traverse Tree to find node to remove
// If Node has both children, dont remove throw error
// If not, remove node and bring up proper child.
int leftChild = 0; // 0 is false 1 is true
int rightChild = 0;
int bothChild = 0; // 0 is false and 1 is true
int compareValue = 0;

if ( ((*tree)->left) != NULL)
leftChild=1;
if ( ((*tree)->right) != NULL)
rightChild=1;
if ( (leftChild==1) && (rightChild==1) )
bothChild = 1;

if (*tree == NULL)
{
printf("\nEmpty Tree Nothing to Remove.\n");
return;
}
compareValue = strcmp(removeData, (*tree)->data);

// String is found and does not have two children
if ( (compareValue == 0) && (bothChild == 0) )
{
if (leftChild == 1)
{
printf("\nData Found, and it has a left Child.");
// Set the left of the parent to the
return;
}

if (rightChild == 1)
{
printf("\nData found, and it has a right child.\n");
return;
}
// Remove Current and Make right the current

else
{
printf("\nData found, and it has no children\n");
return;
}
// Remove Current Node

}

if ( (compareValue == 0) && (bothChild == 1) )
{
printf("\nNode found but has both children, cannot be removed.\n");
}

if ( (compareValue < 0) && (leftChild == 0) )
{
printf("\nData is not in left child of the tree.\n");
return;
}

if ( (compareValue > 0) && (rightChild == 0) )
{
printf("\nData is not in right child of the tree.\n");
return;
}
if ( (compareValue < 0) && (leftChild == 1) )
{
//Go Left while there is a left
printf("\nLeft going remove.\n");
removeNode( &(*tree)->left, removeData);
}

if ( (compareValue > 0) && (rightChild == 1) )
{
//Go right while there is a right
printf("\nRight going remove.\n");
removeNode( &(*tree)->right, removeData);

}
}
int main(void)
{
char menu[] ="\n(1) Add Word\n(2) Delete Word\n(3) Inorder Print\n(4)
Preorder Print\n(5) Postorder Print\n(6) Quit\nYour Choice: ";
int choice=0;
char input[WORD_SIZE];
char removeString[WORD_SIZE];
int debug = 0;

int valid;
node *rootTree, *cursor, *inputNode, *deleteNode;
rootTree = NULL;
cursor = rootTree;
inputNode = NULL;
deleteNode = NULL;

// Begin programatic insert

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "o", WORD_SIZE);
insertNode(&rootTree, &inputNode);
inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "k", WORD_SIZE);
insertNode(&rootTree, &inputNode);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "b", WORD_SIZE);
insertNode(&rootTree, &inputNode);
inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "l", WORD_SIZE);
insertNode(&rootTree, &inputNode);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "g", WORD_SIZE);
insertNode(&rootTree, &inputNode);
inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "r", WORD_SIZE);
insertNode(&rootTree, &inputNode);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "p", WORD_SIZE);
insertNode(&rootTree, &inputNode);
inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "q", WORD_SIZE);
insertNode(&rootTree, &inputNode);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "z", WORD_SIZE);
insertNode(&rootTree, &inputNode);
inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, "j", WORD_SIZE);
insertNode(&rootTree, &inputNode);
// End Programatic Insert

do
{
valid=0;
printf("%s", menu);
scanf("%d", &choice);

if (choice == 1)
{
printf("Enter Word: ");
scanf("%s", &input);

if (debug)
printf("\nYou entered: %s\n", input);

inputNode = (node *)malloc(sizeof(node));
inputNode->left = inputNode->right = NULL;
strncpy(inputNode->data, input, WORD_SIZE);

if (debug)
printf("\nData inserted in tree: %s\n", inputNode->data);

insertNode(&rootTree, &inputNode);
valid=1;
}
else if (choice == 2)
{
printf("Enter Word: ");
scanf("%s", &input);

strncpy(removeString, input, WORD_SIZE);
removeNode(&rootTree, removeString);
valid=1;
}
else if (choice == 3)
{
printf("InOrder Tree: ");
inorder(rootTree);
valid=1;
}
else if (choice == 4)
{
printf("PreOrder Tree: ");
preorder(rootTree);
valid=1;
}
else if (choice == 5)
{
printf("PostOrder Tree: ");
postorder(rootTree);
valid=1;
}
else if (choice == 6)
{
printf("Thank you for using the dictionary manager.\n");
valid=1;
}
else if (valid == 0)
{
printf("\nInvalid Choice please try again!!\n");
}
}while(choice != 6);
free(rootTree);
free(inputNode);
free(cursor);

return 0;
}

Another side note - the code is compiles fine if anyone wants to try
it out and see what happens. Also the tree is set to preinitialize to
some data (for consistency testing purposes).

If you run the code - you will see its just really a matter of somehow
keeping track of the parent.

Can someone just modify the implementation - or post how they would do
it.

[Ben Pfaff]

tj*******@hotmail.com (Tarique Jawed) writes:

Alright I needed some help regarding a removal of a binary search
tree. Yes its for a class, and yes I have tried working on it on my
own, so no patronizing please. I have most of the code working, even
the removal, I just don't know how to keep track of the parent, so
that I can set its child to the child of the node to be removed.

Basically your removal function looks like this:

/* Deletes the node with value DATA from the subtree rooted
at NODE. */
void delete_node(node *node, int data)
{
/* How can I change my parent to point to someone else? */
}

where it's meant to be used as

delete_node(tree_root, data_to_delete);

Your problem is at this level. You need to somehow pass the
change in child pointers to the recursive call above you.
Fortunately, that's pretty easy: just use the return value. So
your function should now look like this:

/* Deletes the node with value DATA from the subtree rooted
at NODE. Returns the node that the parent's child pointer
should now point to. */
node *delete_node(node *node, int data)
{
/* Returns the new node that replaces this one; if no
replacement is necessary, just returns the same node
we were passed. */
}

where it's meant to be used as

tree_root = delete_node(tree_root, data_to_delete);

Does that answer your question?

(Alternatively you could change to an iterative method of tree
deletion. The recursion doesn't really help you much here.
That's what I'd do; see my webpage at
http://adtinfo.org/libavl.html/Deleting-from-a-BST.html
for details.)
--
"When in doubt, treat ``feature'' as a pejorative.
(Think of a hundred-bladed Swiss army knife.)"
--Kernighan and Plauger, _Software Tools_

[Tarique Jawed]

I took ur advice and wrote the method iteratively - I even looked at
your code - but honestly - this is my very first project in C and well
I'm in pointer hell - trying to keep track of who is pointing to what.

I wont post all of the code here as it doesnt make sense - but ive put
it online at

http://sparky.homeunix.com:8000/private/binarytree.c
I'll update it as often as I make any progress.
thanks again
Tarique

P.S. Are you doing ur pHd at standford - impressive work, I also sent
this to your email, b/c of the delay that posting on usenet has for
me.

[CBFalconer]

Tarique Jawed wrote:

I took ur advice and wrote the method iteratively - I even looked at
your code - but honestly - this is my very first project in C and well
I'm in pointer hell - trying to keep track of who is pointing to what.

I wont post all of the code here as it doesnt make sense - but ive put
it online at

http://sparky.homeunix.com:8000/private/binarytree.c

I'll update it as often as I make any progress.

P.S. Are you doing ur pHd at standford - impressive work, I also sent
this to your email, b/c of the delay that posting on usenet has for
me.

It is too bad you spoiled your lucid reply by the use of "ur" for
"your". There is a furious thread going about such unclean
practices.

You can often ease your problems with pointers by suitable type
names. I prefer something like:

typedef struct foo {
/* foo thingies */
} foo, *foop;

so the terminal p identifies a pointer type. You will eventually
develop a style that suits yourself.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[Ben Pfaff]

tj*******@hotmail.com (Tarique Jawed) writes:

I took ur advice and wrote the method iteratively - I even looked at
your code - but honestly - this is my very first project in C and well
I'm in pointer hell - trying to keep track of who is pointing to what.
It really helps to sit down and do a few deletions with paper and
pencil. It also helps to write a function to print out the
structure of a binary tree. Unfortunately I'm not feeling up to
debugging your code at the moment; I'm trying to relax today.
P.S. Are you doing ur pHd at standford - impressive work, I also sent
this to your email, b/c of the delay that posting on usenet has for
me.

Yes, I am working on my Ph.D. at Stanford.
--
"It would be a much better example of undefined behavior
if the behavior were undefined."
--Michael Rubenstein