## Flipkart Interview Question

Senior Software Development Engineers**Country:**India

**Interview Type:**Phone Interview

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!

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;
}
}
}
}
```

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

assuming it is a binary tree

- Amit July 07, 2013o(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;

}