CareerCup

PYTHON.

def max_depth(node) {
    if node == None:
        return (None, 0);
    left, left_depth = max_depth(node.left())
    right, right_depth = max_depth(node.right())
    if left_depth == 0 and right_depth == 0:
        return node, 1
    if left_depth >= right_depth:
        return left, left_depth+1
    return right, right_depth+1

use queue for level order traversal and print the last element .

int deepestNode(tnode *tree){
    int front, rear;
    struct tnode** queue = createQueue(&front,&rear);
    struct tnode *temp = tree;
    struct tnode *prev = tree;
    while(temp!=NULL){
        prev = temp;
        if(temp->left!=NULL){
            enQueue(queue,&rear,temp->left);
        }
        if(temp->right!=NULL){
            enQueue(queue,&rear,temp->right);
        }
        temp = deQueue(queue, &front);
    }
    return prev->value;
}

public void deepest() {
		int h = findHeightofTree(root);
		findDeepestNode(root,h, 0);
		
	}

	private void findDeepestNode(Node root, int h, int depth) {
		if(root==null)
			return ;
		if(root.left==null && root.right==null )
		{
			if(depth+1 == h)
				System.out.println(root.data);
		}
		findDeepestNode(root.left, h, depth+1);
		findDeepestNode(root.right, h, depth+1);
	}

	private int findHeightofTree(Node root) {
		if(root == null)
			return 0;
		
		return (1+Math.max(findHeightofTree(root.left), findHeightofTree(root.right)));

}

public void deepest() {
		int h = findHeightofTree(root);
		findDeepestNode(root,h, 0);
		
	}

	private void findDeepestNode(Node root, int h, int depth) {
		if(root==null)
			return ;
		if(root.left==null && root.right==null )
		{
			if(depth+1 == h)
				System.out.println(root.data);
		}
		findDeepestNode(root.left, h, depth+1);
		findDeepestNode(root.right, h, depth+1);
	}

	private int findHeightofTree(Node root) {
		if(root == null)
			return 0;
		
		return (1+Math.max(findHeightofTree(root.left), findHeightofTree(root.right)));
	}

public void deepest() {
		int h = findHeightofTree(root);
		findDeepestNode(root,h, 0);
		
	}

	private void findDeepestNode(Node root, int h, int depth) {
		if(root==null)
			return ;
		if(root.left==null && root.right==null )
		{
			if(depth+1 == h)
				System.out.println(root.data);
		}
		findDeepestNode(root.left, h, depth+1);
		findDeepestNode(root.right, h, depth+1);
	}

	private int findHeightofTree(Node root) {
		if(root == null)
			return 0;
		
		return (1+Math.max(findHeightofTree(root.left), findHeightofTree(root.right)));
	}

public static int deepestNode(TreeNode node) {
Queue<TreeNode> q = new LinkedList<>();
q.add(node);
// int depth = 0;
TreeNode treeNode = null;
while (q.isEmpty() != true) {
// ++depth;
treeNode = q.remove();
if (treeNode.left != null)
q.add(treeNode.left);
if (treeNode.right != null)
q.add(treeNode.right);
}
System.out.println(treeNode.value);

return treeNode.value;

}

Another attempt in Java. Note that only a leaf node can ever be the deepest node.

class NodeHolder {
  Node node;
  int maxDepth;
}

void traverse(Node root) {
  NodeHolder holder = new NodeHolder();
  _traverse(root, 0, holder);
  return holder.node;
}

void _traverse(Node root, int depth, NodeHolder deepest) {
  if (root == null) return;
  if (root->left == null && root->right == null) {
    if (depth > deepest.maxDepth) {
      deepest.node = root;
      deepest.maxDepth = depth;
    }
  }
  _traverse(root->left, depth + 1, deepest);
  _traverse(root->right, depth + 1, deepest);
}