CareerCup

private static BinaryTreeNode deepestNode(BinaryTreeNode root) {
		BinaryTreeNode temp = null;
		Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
		q.add(root);
		while (!q.isEmpty()) {
			temp = q.poll();
			if (temp.getLeft() != null)
				q.add(temp.getLeft());
			if (temp.getRight() != null)
				q.add(temp.getRight());
		}

		return temp;
	}

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

Maybe in these sort of questions the interviewer expects you to ask. What if there are multiple nodes at the same depth which zporgd's solution totally ignores

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

Why not using level-order Traversal. the last level is the deepest nodes

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