Thread: remove recursion

Why are you posting C++ code on the C board?

Hi, me again!

I tested my code to ensure that everything works (worked - don't know which is correct) fine. Then, only problem was an array of 50 pointers and that was assumption that 50 pointers would be sufficient. So, I wanted to remove that (last) weakness of my code and recalled disscussion between Prelude and me about number of elements in a tree stack. We agreed od (N+1)/2 where N is the number of nodes in a tree (level order).
So I implemented postorder traversal:

Code:

void postorder_it ( node* root )
{
    typedef struct {
    node *item;
    unsigned vleft :1;
    unsigned vright :1;
  } wide_node;
	int size,i;
	int top = 0;
	wide_node* stack; 

	if( root == NULL)
		return;

	size = number_of_nodes(root);
	size = (size + 1)/2;/* pay attention on this line*/

	stack = malloc(size*sizeof(wide_node));

	for(i=0 ; i<size; i++)
	{
		stack[i].item = NULL;
		stack[i].vleft = 0;
		stack[i].vright = 0;
	}
	/* Simplify the root special case */
	stack[top++].item = root;

	while (top > 0 ) 
	{
		/* Move to the left subtree if present and not visited */
		for(;  root->left != NULL && !stack[top].vleft; root=root->left ) 
		{
		stack[top].vleft = 1;
		stack[top++].item = root;
	 
		}  
	
	 /* Move to the right subtree if present and not visited */
		if( root->right != NULL && !stack[top].vright ) 
		{
		stack[top].vright = 1;
		 stack[top++].item = root;
	
		 root = root->right;
		}
		else
		{
			printf("%d ",root->data);
			/* Clean up the stack */

			stack[top].vleft = 0;
			stack[top].vright = 0;

			/* Move up */
			root = stack[--top].item;
		}
	}
	free( stack );/*free stack - it's no longer needed*/
}

I'm using .Net 2002 and executed taht code a couple of times and everything worked as expected. But then, I wanted to check for memory leak, included header <crtdbg.h> and used _CrtDumpMemoryLeaks();

Here problem showed up!
My program after call of free (stack) caused unhandled exception, file dbghep.c opened

Code:

#else  /* WINHEAP */

        /*
         * Go through the heap regions and see if the pointer lies within one
         * of the regions of the local heap.
         *
         * Pointers from non-local heaps cannot be handled. For example, a
         * non-local pointer may come from a DLL that has the CRT linked-in.
         *
         */

        for (i = 0; (base = _heap_regions[i]._regbase) != NULL &&
                i < _HEAP_REGIONMAX; i++)
        {
            if (pUserData >= base && pUserData <
                    (void *)(((char *)base)+_heap_regions[i]._currsize))
                return TRUE;
        }

        return FALSE;

#endif  /* WINHEAP */
} /* here break stoped*/

and I got a message telling me that break was on the last line of above code.

I was trying to realize what happened and then (at first)I figured out what cause it by examining postorder implementation.
I saw root is pushed twice on the stack so my top stacak pointer went out of bounds and changed line:

Code:

size = (size + 1)/2;

to this:

Code:

size = 1+(size + 1)/2;/* make room for extra element*/

Again, I tested and it was OK, the I decided to test degenerate tree and again, exception was there so my last shot for inorder and postorder (as well as height()) . One logical approach was allocating N elements for the stack (where N is number of nodes in the tree).
What happened?

Code:

size = number_of_nodes(root);

stack=malloc(size*sizeof(wide_node))

My program still cause exception in debug mode, while appears to work fine when executed;

Every problem is solved by using this malloc call:

Code:

stack=malloc((1+size)*sizeof(wide_node))

I think this is caused by top pointer which walue at some moment is equal size.
for exampe sequence when inserting in the tree:
{8,7,6,5,4,3,2}

size is 7 and at some moment top is also 7 and lines:

Code:

	stack[top].vleft = 0;
	stack[top].vright = 0;

changes memory byound allocated space. So
two approach are possible:

Code:

if( top != size)
{
	stack[top].vleft = 0;
	stack[top].vright = 0;
}

or simply allocate more memory!
I can only conclude that function free tried to free memory that weren't allocated with malloc call.
Anyway I've fixed problem (in function height too), and like to
here your comments and opinions on this issue!

Conclusion:
if I use postorder as implemented above he/she I'll be needed
stack room for all elements in the tree. What should I do? Maybe try to think some other more clever implementation or what?

Maybe programming is hard just because you can never know what are possible cases your in which program will be used.

I spent entire weekend playing with binary tree and my girlfriend was very unsatisfied.

Prelude, if you're reading this please, can you post postorder implementation wrote in a similar way iterative inorder
is written in your tutorial.
I cannot figure out how to implement postorder similiar to inorder in your tutorial (if this is possible at all)

P.S. Sorry because of monster post but these things are simply thrilling me! I want to share my incremental steps in this solving problem, who knows, maybe someone will find it useful.
Thanks!

>Maybe programming is hard just because you can never know
>what are possible cases your in which program will be used.
Totally.

>can you post postorder implementation wrote in a similar way
>iterative inorder is written in your tutorial.
Okay, that's different from your original goal of writing an iterative inorder traversal using the same style as the iterative postorder traversal. Iterative postorder is much harder, and thus requires more scaffolding to work. So a bunch of nested loops really won't cut it. Consider the following variation:

Code:

void postorder_it(struct node *tree, size_t size)
{
  struct item {
    struct node *p;
    int n;
  } *save;
  int top = 0;

  save = malloc(size * sizeof *save);
  save[top].p = tree, save[top++].n = 0;

  while (top != 0) {
    struct item curr = save[--top];
    if (curr.n == 2)
      printf("%d ", curr.p->data);
    else {
      int dir = curr.n++;
      save[top++] = curr;
      if (curr.p->link[dir] != NULL)
        save[top].p = curr.p->link[dir], save[top++].n = 0;
    }
  }

  free(save);
  printf("\n");
}