CareerCup

The depth of a tree is the length of the longest path from the root to any of the leaves.

So, the following recursive function should do when applied on root:
depth(inner_node) = max(
depth(inner_node->left_child),
depth(inner_node->right_child)
)
+ 1
and
depth(leaf) = 0

int Treedepth(tree* T)
{
if(T==NULL)
{
return -1;
}
return (1+max(Treedepth(T->left),Treedepth(T->right));
}

int maxdepth(tree_node * root)
{
	int d1=0, d2=0;
	if (root == NULL)
		return 0; 
	d1 = maxdepth(root->left);
	d2 = maxdepth(root->right);
	if(d1>d2)
		return d1+1;
	else 
		return d2+1;
}

Can anyone convert this algorithms to a no recursive one ?

no recursion..probably..use graph traversal to count the number of nodes(=x) and take log()x or log(x)+1.

BFS and keep track of levels it traveled

Do a level order traversal or BFS, and count the levels,

typedef struct node{
int data;
struct node *right;
struct node *left;
}Node;

typedef struct {
Node *p;
int level;
}queue;

void levelOrder(Node *ptr) {
if (ptr == NULL) return;
while(!isEmpty() ) {
queue *q = dequeue();
q->level++;
if (q->p->left != NULL) enqueue (q->p->left,q->level);
if (q->p->right != NULL) enqueue (q->p->right,q->level);
}
return ;

}

int findDepth(struct node* T)
{
if(T==NULL)return 0;

else
return(1+max( findDepth(T->left), findDepth(T->right) );

}

can this be done in O(h) h is the height of the tree.??