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:

stack is:Code:12 / \ / \ / \ / \ / \ / \ 6 16 / \ \ 1 10 17 \ 25 / 21 / 18

{12},{16,6},{16,10,1},{16,10},{16},{17} (reset counter to 1),{25},{21},{18}

Here's the code:

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)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 have recursive code:

What I was trying is to remove recursion and wonder if there is some general procedure for removing recursion.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); } }

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!