## Flipkart Interview Question for Senior Software Development Engineers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Instead of returning (x+y+1), shouldn't it return max(x,y)+1

Comment hidden because of low score. Click to expand.
3

@ajit.virus.bit--no i think one of them must be 0..so max(x,y)=x+y..correct me if i am wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

Comment hidden because of low score. Click to expand.
0
of 0 vote

which1 s correct ??

Comment hidden because of low score. Click to expand.
0
of 0 vote

which1 s correct ??

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

your code is maximum depth.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.