CareerCup

Suryaoe could you tell these question are for fresher or 1-2 year experienced ??

@duke
internship

sort the binary tree values descendingly. the maximum one is the root of BST, the second one is the left side of root and etc.
The depth of tree would be O(n). The order of algorithm is O(nlogn).

int largestBST(TreeNode t) {
		if (t == null) {
			return 0;
		}
		if (isBST(t)) {
			return sizeBST(t);
		}
		return Math.max(largestBST(t.getLeftChild()),
				largestBST(t.getRightChild()));
	}

	boolean isBST(TreeNode t){
		if(t == null || (t.getLeftChild() == null && t.getRightChild() == null)){
			return true;
		}
		if (t.getValue() < t.getLeftChild().getValue() || t.getValue() > t.getRightChild().getValue()){
			return false;
		}
		return isBST(t.getLeftChild()) && isBST(t.getRightChild())
	}

	int sizeBST(TreeNode t) {
		if (t == null) {
			return 0;
		}
		if (t.getLeftChild() == null && t.getRightChild() == null) {
			return 1;
		}
		return sizeBST(t.getLeftChild()) + sizeBST(t.getRightChild());
	}
}

Do inorder traversal, at each node check whether child is BST or not. If it is BST, then return the node else recursively traverse the left and right sub tree.