CareerCup

/* height of Binary tree iteratively */
	private static Integer height(BinaryTreeNode root) {
		BinaryTreeNode temp;
		Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
		q.add(root);
		q.add(new BinaryTreeNode(-1));
		int level = 0;
		while (!q.isEmpty()) {
			temp = q.poll();
			if (temp.getData() == -1) {
				if (!q.isEmpty())
					q.add(new BinaryTreeNode(-1));
				level++;
			} else {
				if (temp.getLeft() != null)
					q.add(temp.getLeft());
				if (temp.getRight() != null)
					q.add(temp.getRight());
			}
		}

		return level;
	}

/* height of Binary tree recursively */
	private static Integer heightRecursively(BinaryTreeNode root) {
		int leftHeight, rightHeight;
		if (root == null)
			return 0;
		else {
			leftHeight = heightRecursively(root.getLeft());
			rightHeight = heightRecursively(root.getRight());
			if (leftHeight > rightHeight)
				return leftHeight + 1;
			else
				return rightHeight + 1;
		}
	}

It will compile, but produce the wrong result.

Depends on the type of 'left' and 'right'. I guess, here it would be node, coz left and right can be either another internal node, or a terminal node.

In that case, calling {left.height()} or {right.height()} will be invalid !!