CareerCup

Algorithm:

1. Traverse the tree in level order fashion.
2. Set a flag to 0 initially. Flag is used to check if any leaf node is encountered.
3. Mark end of each level with NULL node.
4. When leaf node is encountered for the first time, set the flag to 1.
5. Traverse tree, and if any non leaf node is occured and flag is already set to 1, then it failes the conditoin
6. If NULL node is encountered indicating the end of a level and If the flag is set indicating leaf node is already occured then verify if queue is empty or not. If not then tree fails the condition.

public boolean check(Node root, int curLevel, int preLevel){
		
		if (root.left==null &&root.right==null){
			// bottom of the tree
			if (preLevel==0||preLevel==curLevel){
				preLevel = curLevel;
				return true;
			}
			return false;
		}else{
			
			//go to left sub tree
			boolean bLeft= false;
			if (root.left!=null){
				bLeft = check(root.left, curLevel+1, preLevel);	
			}
			boolean bRight = false;
			if (root.right!=null){
				bRight = check(root.right, curLevel+1, preLevel);
			}
			
			return bLeft&&bRight;			
		}

}

Does it means that checking if the max_depth = min_depth?

We can check the height of the immediate leftchid rightchild and save these values in 2 integers. Then check if the 2 ints are the same. If yes, then the leaves are at the same level otherwise not

class BT
	{
		public bool areAllLeavesAtSameLevel(Node root)
		{
			int levelOfLastLeaf = -1;
			Queue q = new Queue();
			q.enqueue(new NodeLevel(root, 0));
			while(!q.isEmpty())
			{
				NodeLevel nl  = q.dequeue();

				if(nl.node.getLeft() == null && nl.node.getRight() == null)
				{
					if(levelOfLast < 0)
					{
						levelOfLastLeaf = nl.level;
					}
					
					if(nl.level != levelOfLastLeaf)
					{
						return false;
					}
				}				

				if(nl.node.getLeft() != null)
				{
					q.enqueue(new NodeLevel(nl.node.getLeft(), nl.level + 1));
				}

				if(nl.node.getRight() != null)
				{
					q.enqueue(new NodeLevel(nl.node.getRight(), nl.level + 1));
				}
			}
			return true;
		}
	}

	class NodeLevel
	{
		public Node node;
		public int level;
	}

Found the interesting answer for the same.
geeksforgeeks.org/check-leaves-level/

Algo
Post order traversal

1) if null node, return (0, true)
2) if leaf node, then return (level, true)
3) call each subtree with level+1;
4) at any node, if level return by either subtree is non-zero and not equal , then return false.
5) at any node, if either subtree level is zero, return (non-zero level, true)

pair<int, bool> leafLevel (tree *root, int level)
{
	if (!root)
	{
		return make_pair(0, true);
	}
	if (leaf_node)
	{
		return make_pair(level, true);
	}
	pair<int, bool> leftT, rightT;
	leftT = leafLevel (root->left, level+1);
	if (leftT.second == false)
		return make_pair (-1, false);

	rightT = leafLevel (root->right, level+1);
	if (rightT.second == false)
		return make_pair (-1, false);

	if (leftT.first == 0 || rightT.first == 0)
	{
		int level = (leftT.first != 0) ? (leftT.first):(rightT.first);
		return make_pair (level, true);
	}
	if (leftT.first == rightT.first)
	{
		return make_pair (level, true);
	}
	else
	{
		return make_pair (-1, false);
	}
}

BFS version without recursion
1. Go through the tree level by level
2. Find level of the first leaf
3. For each next leafs check level, if levels are different, return false
4. At the end of BFS return true,

public static bool OnSameLevel(Tree tree)
        {
            if (tree == null)
            {
                return true;
            }

            var from = new Queue<Tree>();
            var to = new Queue<Tree>();
            from.Enqueue(tree);

            var levelOfFirstLeaf = -1;
            var currentLevel = 1;

            while (from.Count > 0 || to.Count > 0)
            {
                var node = from.Dequeue();

                if (node.Left != null)
                {
                    to.Enqueue(node.Left);
                }

                if (node.Right != null)
                {
                    to.Enqueue(node.Right);
                }

                // leaf node process
                if (node.Left == null && node.Right == null)
                {
                    if (levelOfFirstLeaf == -1)
                    {
                        // we found first level with leaf node
                        levelOfFirstLeaf = currentLevel;
                    }
                    else
                    {
                        // we found leaf node again, if this one the other level, then return false
                        if (levelOfFirstLeaf != currentLevel)
                        {
                            return false;
                        }
                    }
                }

                if (from.Count != 0)
                {
                    continue;
                }

                // switching to the next level
                currentLevel++;
                var tmp = from;

                from = to;
                to = tmp;
            }

            // all leafs on the same level
            return true;
        }

int check_nodes(struct node *tree)
{
static int depth1,depth2;
if((depth1==depth2!=0)&& tree==NULL)
return 0;
else
if(tree!=NULL) {
check_nodes(tree-->left,depth1++);
check_nodes(tree-->right,depth2++);
}


else if(depth1==depth2)
return 1;

else if(depth1!=depth2)
return 0;

}

Make preorder traversal and for each leaf count its depth. In a separate variable keep the level of the previously found leaf. When you reach next leaf compare its depth with the previous one.
Code:

Integer lastLevel = null;

public boolean checkDepth(Node n, int level) {
	if (n.left == null && n.right == null) {
	    if (lastLevel == null || lastLevel.equals(level)) {
			lastLevel = level;
			return true;
	    }
	    return false;
	}
	boolean result = true;
	if (n.left != null) {
	    result = checkDepth(n.left, level + 1);
	}
	if (result == true && n.right != null) {
	    result = checkDepth(n.right, level + 1);
	}
	return result;
}