CareerCup

/*There may Different method in util.Queue class 
i have not rember name of these method so i have used another method name but the code is correct.....*/
import java.uti.Queue;
class Node
{
    Node left;
    int item;
    Node right;
}
class Tree
{
    public int calculateHigh(Node n)
    {
        Queue<Node> q=new Queue<Node>();
        if(n==null)
        return 0;
        q.add(n)
        q.add(null);
        int high=0;
        while(q.isEmpty())
        {
            Node temp=q.getFirst();
            if(temp==null)
            {
                /*Put marker for next Level*/
                high++;
                if(!q.isEmpty())
                {
                    q.add(null);
                }
            }
            else
            {
                if(temp.left!=null) q.add(temp.left);
                if(temp.right!=null) q.add(temp.right);
            }
        }
        return high;
    }
    public static void main(String arg[]){}
}

Level Order Traversal.
C++ Version:

int getHeightOfBinaryTree ( NODE* root ) {
	if ( !root )
		return 0 ;
		
	int level = 0 ;
	Queue *Q = CreateQueue() ;
	
	Q->enQueue( root ) ;
	Q->enQueue( NULL ) ; //To Mark End of Level
	
	while ( !Q->isEmpty() ) {
		NODE * node = Q->deQueue() ;
		
		if ( NULL == node ) {
			if ( !Q->isEmpty() )
				Q->enQueue( NULL ) ;
			level++ ;
		}
		else {
			if ( node->left )
				Q->enQueue ( root->left ) ;
			
			if ( node->right )
				Q->enQueue ( root->right ) ;
		}
	}
	return level ;
}

O(N) Time and Space Complexity

What about considerations for memory consumption in all cases.
Bfs:
Balanced: n/2
Straight line: 1
Only left child has children: 2
Dfs:
Balanced: 2 ( log n + 1)
Straight line: 1
Only left child has 2 children: n / 2

If the tree structures are more likely to be balanced, then a Dfs approach would be best:

class TreeNode {
  int value;
  TreeNode left,  right; 
}

class PartAns{
  TreeNode node;
  int depth;
  PartAns (TreeNode n, int d){
    node = n;
    depth = d;
  }
}
...
  public int height (TreeNode root){
    if (root==null){
      return null; 
    }
    in maxDepth = 0;
    Stack <PartAns> unchecked = new Stack <PartAns>();
    PartAns a = new PartAns (root, 1);
    unchecked.push (a );
    int d;
    TreeNode n;
    while (!unchecked.isEmpty ()){
      a = unchecked.pop ():
      d = a.depth; 
      if (d > maxDepth)
        maxDepth = d;
      n = a.node.right; 
      if (n != null)
        unchecked.push (new PartAns (n, d+1));
      n = a.node.left; 
      if (n != null)
        unchecked.push (new PartAns (n, d+1));
    }
    return maxDepth;
  }

/*
	 * Depth of a tree without recursion
	 */
	public void depthIter(TreeNode node){
		Stack<TreeNode> stack = new Stack<TreeNode>();
		int ht=0, max=0;
		boolean flag=false;
		stack.push(node);
		while(!stack.empty()){
			flag = false;
			node = stack.pop();
			if(node.rightChild!=null){
				stack.push(node.rightChild);
				flag = true;
			}
			if(node.leftChild!=null){
				stack.push(node.rightChild);
				flag=true;
			}
			
			if(flag){
				++ht;
				if(ht>max)
					max = ht;				
			}else{
				ht--;
			}				
		}
		System.out.println("max depth: "+max);
	}

Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        int h = 0;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.l;
            }
            h = Math.max(h, stack.size() - 1);
            current = stack.pop();
            if (current != null) {
                if (current.r != null) {
                    stack.push(null);
                    current = current.r;
                } else {
                    current = null;
                }
            }
        }

int maxDepthBTNonrecursive(BinaryNode1* ai_bn)
{
   typedef std::pair<BinaryNode1*, int> DepthStackValue;
   typedef std::stack<DepthStackValue> DepthStack;
   DepthStack stack;

   int maxHeight = 0;

   stack.push(std::make_pair(ai_bn, 1));
   
   while (!stack.empty())
   {
      DepthStackValue ai_bn = stack.top();
      stack.pop();

      if (ai_bn.second > maxHeight)
         maxHeight = ai_bn.second;

      if (ai_bn.first->right != nullptr)
         stack.push(std::make_pair(ai_bn.first->right, ai_bn.second + 1));

      if (ai_bn.first->left != nullptr)
         stack.push(std::make_pair(ai_bn.first->left, ai_bn.second + 1));
   }

   return maxHeight;
}