remove recursion

Hello, I'm writing function for determining height of a binary search tree.

Height of a tree is (max number of nodes on the longest path -1).
I wrote code and it seems it works fine. Basic algorithm is to visit nodes, place nodes on a stack and increase counter every time when something is pushed on a stack. When nothing is pushed on a stack counter is not increased. Counter needs to be reseted when search switch to roots right subtree.
Example:

Code:

---

 
                          12
                      /  \
                      /    \
                    /      \
                    /        \
                  /          \
                  /            \
                6                16
                / \              \
              1  10              17
                                    \
                                    25
                                    /
                                  21
                                  /
                                18

---

stack is:
{12},{16,6},{16,10,1},{16,10},{16},{17} (reset counter to 1),{25},{21},{18}
Here's the code:

Code:

---

int height(node* root)
{
        int max=0;
        int counter=0;
        node* stack[50]; /* stack of nodes, assumption 50 is sufficient*/
        int p=0,push;
        node* walk;

        if(root == NULL)
        {
                return -1;
        }
        stack[p++] = root;

        while(p > 0)
        {
                push = 0;/* flag indicate that node is pushed on the stack*/
                walk = stack[--p];
               
                if(walk->left || walk->right)/* node(s) will be pushed on the stack*/
                {
                        counter++;/* increment counter*/
                        if(max < counter)
                                max = counter;
                }
                if(walk->right != NULL)
                {
                        stack[p++] = walk->right;
                        push = 1;/* indicate push operation*/
                }       
                if(walk->left != NULL)
                {
                        stack[p++] = walk->left;
                        push = 1;
                }
                if(p==1 && push == 0)/* reset counter - start counting in the root's right subtree*/
                        counter=1;
        }
        return max;
}

---

I think this does the job, but if you can examine and give me advice if something can be done different (i.e. more efficient)

I have recursive code:

Code:

---

int height(struct node* node) {
        if (node==NULL) {
        return(-1);
        }
        else {
        /* compute the depth of each subtree*/
        int lDepth = height(node->left);
        int rDepth = height(node->right);
        /*use the larger one*/
        if (lDepth > rDepth) return(lDepth+1);
        else return(rDepth+1);
        }
}

---

What I was trying is to remove recursion and wonder if there is some general procedure for removing recursion.
Each time I need to rewrite recursive function to iterative I spend a lot of time debugging. There must be some general procedure, or at least some special cases where this job is straightforward. Can you help me with this issue?
Thanks!

I've just checked, my iterative solution of finding height of a tree has bug. For example, if binary tree is made by inserting this sequence:
20,10,31,5, 12, 24, 38,1,8,11,14,13,16,18,33,32
iterative function return 6 instead of 5.
I really don't know how to write correct function. I've already spent many hours but not able to correct this problem.
I'd really appreciate any help.

Removing recursion from binary tree functions (is usually silly :D) follows a nice pattern. If you've ever written an iterative postorder traversal for a binary tree then you can use the same principles and techniques for this task. Notice how the operations are the same when generalized:

Go left
Go right
Do something

Thanks, Prelude
I found your code by serching the board.

Code:

---

void postorder ( struct node *tree, void (*action) ( struct node *node ) )
{
  struct {
    struct node *item;
    unsigned vleft :1;
    unsigned vright :1;
  } stack[50] = {0};
  int top = 0;

  /* Simplify the root special case */
  stack[top++].item = tree;

  while ( top != 0 ) {
    /* Move to the left subtree if present and not visited */
    if ( tree->left != NULL && !stack[top].vleft ) {
      stack[top].vleft = 1;
      stack[top++].item = tree;
      tree = tree->left;
      continue;
    }

    /* Move to the right subtree if present and not visited */
    if ( tree->right != NULL && !stack[top].vright ) {
      stack[top].vright = 1;
      stack[top++].item = tree;
      tree = tree->right;
      continue;
    }

    action ( tree );
   
    /* Clean up the stack */
    stack[top].vleft = 0;
    stack[top].vright = 0;

    /* Move up */
    tree = stack[--top].item;
  }
}

---

and mange to solve my problem.
However a new question come up.
I'm trying to implement inorder in similar way you implemented postorder
go left
visit
go right
here's my shot:

Code:

---

void inorder_it ( node *tree )
{
  struct {
    struct node *item;
    unsigned vleft :1;
    unsigned vright :1;
  } stack[50] = {0};
  int top = 0;

  /* Simplify the root special case */

  stack[top++].item = tree;

  while ( top != 0 ) {
    /* Move to the left subtree if present and not visited */
    if ( tree->left != NULL && !stack[top].vleft) {
        stack[top].vleft = 1;
      stack[top++].item = tree->left;
      tree = tree->left;
      continue;
    }

        tree = stack[--top].item;
        printf("%d ", tree->data );
       
    /* Move to the right subtree if present and not visited */
    if ( tree->right != NULL && !stack[top].vright ) {
    stack[top].vright = 1;
      stack[top++].item = tree->right;
      tree = tree->right;
      continue;
    }
       
  }
}

---

but I have a small problem. for instance if BST is made using this sequence:
41,34,67,0,24,58,69,62,78,64

My function prints:
0 24 34 41 67 and then finishes.
I assumes it has something to do with flags, but don't know what.
Please, help.

>Please, help.
Search the FAQ (Binary Search Trees part 1) and you'll find that I covered non-recursive inorder traversal. :)

Quote:

---

Originally Posted by Prelude

>Please, help.
Search the FAQ (Binary Search Trees part 1) and you'll find that I covered non-recursive inorder traversal. :)

---

Yes, I know that, I've read it, but I want to implement inorder in similar fashion you implemented postorder traversal with bit flags.

Anyway I manage to do something, if you could only verify it:

Code:

---

void inorder_it ( node *tree )
{
  struct {
    struct node *item;
    unsigned vleft :1;
    unsigned vright :1;
  } stack[50] = {0};
  int top = 0;

  /* Simplify the root special case */

  stack[top++].item = tree;

  while ( top != 0 ) {
    /* Move to the left subtree if present and not visited */
    if ( tree->left != NULL && !stack[top].vleft) {
                stack[top].vleft = 1;
                stack[top++].item = tree->left;       
                tree = tree->left;
                continue;
    }

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

---

>I want to implement inorder in similar fashion you implemented postorder traversal with bit flags.
Whatever floats your boat. :)

>if you could only verify it
Looks okay to me.

and final conclusion,
height function:

Code:

---

void height_it ( node* tree )
{
  struct {
    node *item;
    unsigned vleft :1;
    unsigned vright :1;
  } stack[50] = {0};
  int top = 0;
  int counter = 0;
  int max = 0;

  if( tree == NULL)
          return;
  /* Simplify the root special case */
  stack[top++].item = tree;

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

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

                /* Move up */
                tree = stack[--top].item;
                counter--;
        }
  }
return max;
}

---

I think this code does the job!

>I think this code does the job!
You think? Don't think, test. :) Continue to test until you can say "This code does the job!" and when I say "Are you sure?" you can confidently reply "Yes!".

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

Quote:

---

Originally Posted by Micko

Code:

---

cout<< ( tree->data )<< " ";

---

---

You're right itsme86! But we could easily change that to:

Code:

---

printf("%s\n", tree->data);

---

Quote:

---

Originally Posted by itsme86

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

---

So sorry guys! My mistake, I originally wrote function in C++ and forgot to change to printf when pasting .
It won't happen again!

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");
}

---