CareerCup

assuming it is a binary tree
o(n) time complexity soln
int depth(root,node)
{
if(!root)
return 0;
if(root==node)
return 1;
int x=depth(root->left,node),y=depth(root->right,node);
if(x || y)
return x+y+1;
return 0;
}

If the parent-child relationship is available, we can do:

depth=0;
while(node!=root)
{
depth++;
node=parent[node];
}

In case we don't have this information on our disposal, we can run DFS from root:

depth[root]=0;

dfs_visit(root,node);

int dfs_visit(root,node)
{
color[root]=1;
for(i=0;i<n;i++)
{
if(graph[n][i]!=inf && color[i]==0)
{
parent[i]=n;
depth[i]=depth[parent[i]]+1;
if(i==node)
 return depth[i];
dfs_visit(i,node);
}
}
}

Please let me know if there is a mistake in this pseudo code, thanks!

which1 s correct ??

which1 s correct ??

Pseudo Code

int find_nodedepth (root,node){
	if(root==NULL){				// Base Condition node not found;
		return 0;
	}
	else if(root==node){			// Best Condition node found at root with depth 1
			return = 1;
		}
		else{
			l = find_nodedepth(root->lchild,node); // Ask left subtree if it has the node 
											 // and if yes at what depth
			r = find_nodedepth(root->rchild,node);// Ask right subtree if it has the node 
											 // and if yes at what depth
			if( max(l,r) > 0 ){		// to check if node is found or not returns 0 if not found
								// otherwise return the depth
				return max(l,r) + 1;
			else {
				return 0;
				}
			}
		}
}

private static int finddepthOfNode(BTreeNode root,BTreeNode node,int depth){
if(root == null)
return 0;
if(root.item == node.item)
return depth;
int deep = finddepthOfNode(root.left,node,depth+1);
if(deep != 0)
return deep;
deep = finddepthOfNode(root.right,node,depth+1);
return deep;

}

int height(root); // suppose we have this 

int depth_of_node(struct node *root, int key) {
	int i;
	int h=height(root);
    for(i=1;i<=h;i++) {
        search_levelorder(root,key,i);
		if(found) {
			return i;
		}
    }
}

void search_levelorder(struct node *root, int key, int depth) {
	if(depth == 1) {
    	if(root->data == key) {
			found = 1; 
 			return;
 		}
    }
	search_levelorder(root->left, key, depth-1);
	search_levelorder(root->right,key,depth-1);
}

int height(root); // suppose we have this 

int depth_of_node(struct node *root, int key) {
	int i;
	int h=height(root);
    for(i=1;i<=h;i++) {
        search_levelorder(root,key,i);
		if(found) {
			return i;
		}
    }
}

void search_levelorder(struct node *root, int key, int depth) {
	if(depth == 1) {
    	if(root->data == key) {
			found = 1; 
 			return;
 		}
    }
	search_levelorder(root->left, key, depth-1);
	search_levelorder(root->right,key,depth-1);
}

if it is a BST,we can follow LCA approach..o(depth) time complexity

int depth(root,node)
{
if(root == NULL)
return 0;
return 1+max(depth(root->left,node),depth(root->right,node));
}