CareerCup

I think it's simple, you can recursively solve this problem. I'd break down it in two phases:
1. when we go down the tree recursively, maintain a variable "level" which will store the current node level in the tree.

getDeepestOdd(root->left, level+1); // go left
getDeepestOdd(root->right, level+1); // go right

2. after 1st step, we will hit the leaves of the tree, if it is a leaf and level is odd return the level, else return 0

if(root->left == NULL && root->right == NULL) {
        if(level%2 == 0) return 0; 
        else return level; 
    }

3. while coming from bottom to top take the max from both left and right subtree

return max(getDeepestOdd(root->left, level+1), 
                getDeepestOdd(root->right, level+1));

Full Code:

int getDeepestOdd(node *root, int level){
    if(root == NULL) return 0;
    
    // if we encounter a leaf
    if(root->left == NULL && root->right == NULL) {
        if(level%2 == 0) return 0; // if even level, return 0
        else return level; // else return the level 
    }
    return max(getDeepestOdd(root->left, level+1), 
                getDeepestOdd(root->right, level+1));
}

If you want, you can run the code on ideone @ ideone.com/0k45Ed

Since we are looking for the deepest node(I misread the question, which only asks for the depth, not the node itself, but will leave this here), doing a depth first search might be preferable, considering space complexity, as the time complexity will be similar, as compared to doing a breadth first search. And writing the code for a recursive version of dfs might be easier.

Assume root is at depth 1 (this assumption matters, and needs to be clarified with the interviewer).

We do a dfs, and keep track of the level and a possible candidate node (and its depth). Possible code (C/C++ like).

Tree * FindOddDeep(Tree * root) {
    uint depth=1; // unsigned int
    Tree *result = NULL;
    unsigned int result_depth = 0;
    FODHelper(root, depth, *result, result_depth);
    return result; 
}
  
void FODHelper
(Tree *root, uint &depth, Tree ** pResult, uint &result_depth) {
    if (root == NULL) {return;}
   
    // A leaf node
    if (root->left == NULL && root->right == NULL) {
        if (depth % 2 == 1) { // odd depth
            if (depth > result_depth) { // deeper than current candidate
                *pResult = root;
                 result_depth = depth;
            }
        }
        return;
    }
    depth++;
    FODHelper(root->left, depth, pResult, result_depth);
    FODHelper(root->right, depth, pResult, result_depth);
    depth--;
}

As others have mentioned, you need to clarify with the interview what constitutes the depth of a leaf, but at the end of the day, it's a simple recursion:

def test():
    assert 0 == max_odd_leaf_depth(None)
    assert 1 == max_odd_leaf_depth((None, 1, None))
    assert 0 == max_odd_leaf_depth(((None, 2, None), 1, (None, 2, None)))
    tree3 = (None, 3, None)
    tree2 = (tree3, 2, tree3)
    tree1 = (tree2, 1, tree2)
    assert 3 == max_odd_leaf_depth(tree1)

def max_odd_leaf_depth(tree, depth=1):
    # return 0 if no leafs at an odd
    # depth
    if not tree:
        return 0
    right, val, left = tree
    if not right and not left:
        # overly fancy way of saying
        # return 0 for even, depth for odd
        return depth * (depth % 2)
    child_depths = [
        max_odd_leaf_depth(left, depth+1),
        max_odd_leaf_depth(right, depth+1)
    ]
    return max(child_depths)

test()

You'd initially call this with level = 1 since the root of a tree is at level 1.

TreeNode deepestOddLeaf(TreeNode t, int rightLevel, int leftLevel){
    if(t == null){
        return null;
    }
    TreeNode right, left;
    if(t.left != null) {
        left = (t.left, leftLevel++, rightLevel);
    }
    else if(t.right != null) {
        right = (t.left, leftLevel, rightLevel++);
    }
    else {
        if (leftLevel % 2 == 0) {
            return null;
        }
        if (rightLevel % 2 == 0){
            return null;
        }
        if (leftLevel > rightLevel) {
            return left;
        else {
           return right;
        }
    }

_DeepestOddlevelleaf(node, currentlevel, int & deepestoddlevel)
	{
		if (currentlevel is odd 
			&& node is a leafnode 
			&& currentlevel > deepestoddlevel)
		{
			deepestlevel = currentlevel;
		}
		if (node->left)  	
			_DeepestOddlevelleaf(node->left, currentlevel+1, deepestoddlevel);
		if (node->right)  	
			_DeepestOddlevelleaf(node->right, currentlevel+1, deepestoddlevel);		
	}

	DeepestOddlevelleaf()
	{
		deepestoddlevel = 0;
		if (root != null)
		_DeepestOddlevelleaf(root, 1, deepestoddlevel);

		return deepestoddlevel;
	}

Working code

#include<iostream>
#include<vector>
#include<algorithm>
struct node {
	int value;
	struct node *left;
	struct node *right;

	node(int a) {
		value = a;
		left = NULL;
		right = NULL;
	}
};
node *createBST(std::vector<int> numbers, int low, int high) {
	// create tree from numbers
	if (low > high) return NULL;

	int mid = (low + high) / 2;
	node *root = new node(numbers[mid]);
	root->left = createBST(numbers, low, mid -1);
	root->right = createBST(numbers, mid+1, high);
	return root;

}
int getMaxOddHeight(node* root, int height) {
    static int maxoddheight = -1;
    if(root == NULL) {
        return 0;
    }
    (void) getMaxOddHeight(root->left, height +1 );
    // Print the tree on the console 
    for(int i = 1; i <= height; i++) 
        std::cout << "\t";
    std::cout << root->value << "\n";
    // check if we are at an odd height greater than the current maxoddheight
    if((height %2) != 0 && height > maxoddheight) {
        maxoddheight = height;
    }
    (void) getMaxOddHeight(root->right, height +1 );
    return maxoddheight;
}
void printNodeWithMaxOddHeight(node* root, int height, int maxoddheight) {

    if(root == NULL) {
        return;
    }
    (void) printNodeWithMaxOddHeight(root->left, height +1, maxoddheight);
    
    if(height == maxoddheight) {
        std::cout << "max odd height is " << maxoddheight << " nodes are \n" << root->value << "\n";
    }
    (void) printNodeWithMaxOddHeight(root->right, height +1, maxoddheight);
}
int main() {
	std::cout << "Enter numbers\n";
	std::vector<int> numbers;
	int temp;
	while(std::cin >> temp) {
		numbers.push_back(temp);
	}

	std::sort(numbers.begin(), numbers.end());

	node *root = createBST(numbers, 0, numbers.size() - 1);

    int maxoddheight = getMaxOddHeight(root, 1);

    printNodeWithMaxOddHeight(root, 1, maxoddheight);

}

struct node
{
	int data;
	struct node *left,*right;
}*root=NULL;
int h1;
typedef struct node NODE;

//============================================
//h1 is global variable that will be accessed inside main and will contain height of tree.

void height(NODE *ptr,int h)
{
	if(ptr->left!=NULL)
		height(ptr->left,h+1);
	if(ptr->right!=NULL)
		height(ptr->right,h+1);

	if(ptr->left==NULL && ptr->right==NULL && h%2==1)
		h1=h;	
	
}