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

O(N) time complexity in worst case (unbalanced tree)
O(N) space complexity in worst case (unbalanced tree)

int maxDepth(Tree head){
        return head == null ? 0 : Math.max(maxDepth(head.left), maxDepth(head.right)) + 1;
}

I'm wondering if this would work?
O(n) time complexity
O(1) space complexity

int maxDepth(Tree head)
{
int max=0;
if(head != NULL)
{
max = traverse(head,1);
}
return max;
}

int traverse(Tree node,int depth)
{
if(node == NULL)
return depth;

depth++;
int depthL = traverse(head->left,depth);
int depthR = traverse(head->right,depth);

return max(depthL,depthR);
}

public static int GetMaxDepth(Node root)
{
	if(root == null)
		return 0;

	int left = GetMaxDepth(root.Left);
	int right = GetMaxDepth(root.Left);

	return 1 + ((left > right)?left:rigth);
}

max depth = number of levels.
One can do level order traverse to find out the number of levels.

max depth = number of levels.
One can do level order traverse to find out the number of levels.

max depth = number of levels.
One can do level order traverse to find out the number of levels.

max depth = number of levels.
One can do level order traverse to find out the number of levels.

int Depth(TreeNode* pRoot)
{
if (!pRoot)
return 0;
int l = Depth(pRoot->LeftChild);
int r = Depth(pRoot->RightChild);
return 1 + max(l, r);
}

int maxdepth(node *root){

if(root == NULL){
return 0;
}

if(root->left == NULL && root->right == NULL){
return 1;
}
int left = 1 + maxdepth(root->left);
int right = 1 + maxdepth(root->right);

if(left > right){
return left;
}else{
return right;
}
}

int maxdepth(node *root){
	
	if(root == NULL){
		return 0;
	}
	
	if(root->left == NULL && root->right == NULL){
		return 1;
	}
	int left = 1 + maxdepth(root->left);
	int right = 1 + maxdepth(root->right);
	
	if(left > right){
		return left;
	}else{
		return right;
	}
}

void                                                                                                                                                                                
max_depth(node * r, int level, int& max) {                                                                                                                                          
    if (r == nullptr) {                                                                                                                                                             
        if (level > max) {                                                                                                                                                          
            max = level;                                                                                                                                                            
        }                                                                                                                                                                           
                                                                                                                                                                                    
        return;                                                                                                                                                                     
    }                                                                                                                                                                               
                                                                                                                                                                                    
    max_depth(r->left, level+1, max);                                                                                                                                               
    max_depth(r->right, level+1, max);                                                                                                                                              
}                                                                                                                                                                                   
                                                                                                                                                                                    
int                                                                                                                                                                                 
max_depth(node * r) {                                                                                                                                                               
    int max = 0;                                                                                                                                                                    
    max_depth(r, 0, max);                                                                                                                                                           
    return max;                                                                                                                                                                     
}

What is meant by depth?
A number of nodes to go through til we reach a leaf node starting from the root?
Example

Nodes: {A,B,C,D,E,F,G,H} Edges: {(A,B) (A,C) (B,D) (B,E) (E,F) (E,G) (F,H)}

The depth of H is 4?
The depth of G is 3?
One idea that comes to mind is the depth first search algorithm.
Below are things that I would add to the depth first search.
1. Each time we hop to a new child node we increment a distance variable.
2. Once we have reached the end of a branch (ie a leaf or a node that has
no children) we could compare the distance variable incremented thus far
to some variable container called maximum.
If it is bigger than maximum we replace the maximum thus far with this new distance value.
3. Once we go back up a traversed branch to discover a new branch in the
tree as the algorithm would, how would we account for the new distance?
Example

Nodes:{A,B,C,D,E,F} Edges:{(A,B) (A,C) (C,D) (C,F) (D,E)}

i. we traverse to B and have our max depth as 1 so far.
ii. we go back up the tree to start back at the head and go down
the right side of the binary tree. Now the new distance should be recalculated
but how do we know it should be set to 0? In this case we are at the head so
one could set back to 0 whenever we get back up to head. But there is
a better idea and I will get to it at step iiii.
iii. We discover E and recalculate the maximum to be 3.
iiii. As we go back up the branch up to C. How do we know that the distance should be set to 1 before discovering F and incrementing it to 2?

One idea is for every hop we go DOWN the tree, we INCREMENT distance by 1 BUT every time we hop UP, we DECREMENT distance by 1.
The worst time complexity would be that of depth first search, depth first search goes through all leaves before terminating. We NEED to get to all leaves to do a fair comparison of all the potential depths to find the maximum depth.