Thread: Help with insert/delete binary search tree

You're right... Actually, what I mean was that I wasn't using recursion in the sense of returning a value, instead, I pass the address of structure as an argument. I misunderstood what I wanted to say...

Someone else suggested me to use iteration over recursion because of possible stack problems. But I have no clue on how could I do a delete function of a binary search tree, or even just a "print-all-nodes-and-childs" functions without using recursion. I can do that with a linked-list, I just need to use "while" one time, but for a binary search tree with 2 childs? How do I do that? Also, the same person said something about freeing a pointer and then deferencing it:

Code:

free(cliPtr);

cliPtr->clientProfile = NULL;

Is there anything wrong with this?

Originally Posted by Nazgulled

Someone else suggested me to use iteration over recursion because of possible stack problems. But I have no clue on how could I do a delete function of a binary search tree, or even just a "print-all-nodes-and-childs" functions without using recursion. I can do that with a linked-list, I just need to use "while" one time, but for a binary search tree with 2 childs? How do I do that? Also, the same person said something about freeing a pointer and then deferencing it:

Code:

free(cliPtr);

cliPtr->clientProfile = NULL;

Is there anything wrong with this?

Hadn't looked close enough to notice that. Yeah that's a bad thing to do. If you're lucky it might work a few times, but then it'll go boom sooner or later. You must not access or write to a structure after it has been freed.
In this case you can just delete this line:

Code:

cliPtr->clientProfile = NULL;

There's no point setting something to NULL when it's going out of existence.

Converting tail-recursion into iteration is not particularly hard. However if the function makes two recursive calls then only one of them can be turned into iteration.

I'll illustrate how one can make a tree node counting function semi-iterative.
Double Recursion:

Code:

// Returns the number of items in the tree
int TreeCount(const TItem *head) {
	int count = 0;
	if (head != NULL) {
		//recursively count left nodes (add one for this node)
		count += TreeCount(head->left) + 1;
		//recursively count right nodes
		count += TreeCount(head->right);
	}
	return count;
}

Semi Iterative / Semi Recursive:

Code:

// Returns the number of items in the tree
int TreeCount(const TItem *head) {
	int count = 0;
	while (head != NULL) {
		//recursively count left nodes (add one for this node)
		count += TreeCount(head->left) + 1;
		//iteratively count right nodes
		head = head->right;
	}
	return count;
}

Originally Posted by Nazgulled

Hum... When I use free on something and if in the next line I try to print it's value anyways, the value will still be there,

How do you know it?
memory does not belongs to your program - it is returned to the memory pool...

if this free just returned the last chunk of the memory in some page - the whole page could be already returned to the OS making any address inside this page not available to the program at all.

So even read operation from this address could cause a GPF