## Yahoo Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

```
Item* get_deepest_node(Item* root) {
int max_level = -1;
Item* node = NULL;
get_deepest_node(root, 0, &max_level, &node);
return node;
}
void get_deepest_node(Item* root, int curr_level, int* max_level, Item** node) {
if (!root)
return;
if (curr_level > *max_level) {
*max_level = curr_level;
*node = root;
}
get_deepest_node(root->left, curr_level+1, max_level, node);
get_deepest_node(root->right, curr_level+1, max_level, node);
}
```

#include<iostream>

using namespace std;

struct node

{

int val;

node *left;

node *right;

}*root, *dNode;

int dlevel = 0;

node *creategraph(int k)

{

node *temp= new node;

temp->val=k;

temp->left=NULL;

temp->right=NULL;

return temp;

}

void deepestNode(node *r, int level)

{

if(r==NULL)

return;

if(dlevel < level){

dNode = r;

dlevel = level;

}

deepestNode(r->left, level+1);

deepestNode(r->right, level+1);

}

This is my solution.

```
public BNode DeepestNode(BST bst)
{
Queue<BNode> q = new Queue<BNode>();
BNode deepest = null;
q.Enqueue(bst.Root);
while(q.Count() > 0)
{
deepest = q.Dequeue();
if(deepest.LeftChild != null)
{
q.Enqueue(deepest.LeftChild);
}
if(deepest.RightChild != null)
{
q.Enqueue(deepest.RightChild);
}
}
return deepest;
}
```

- Vir Pratap Uttam May 04, 2015