The following code should check if a given binary tree is a BST. However, for some trees, it

returns the wrong answer.

public static boolean brokenIsBST(TreeNode T)

{

if (T == null)

{

return true;

}

else if (T.left != null && T.left.val > T.val ||

T.right != null && T.right.val < T.val)

{

return false;

}

else

{

return brokenIsBST(T.left) && brokenIsBST(T.right);

}

}

a) Give an example of a binary tree for which brokenIsBST fails.

b) Now, write isBST that fixes the error encountered in part a)

Hint: You will find Integer.MIN_VALUE and Integer.MAX_VALUE helpful.

public static boolean isBST(TreeNode T)

{

return isBSTHelper(T, Integer.MIN_VALUE, Integer.MAX_VALUE);

}

public static boolean isBSTHelper(TreeNode T, int min, int max)

{

//todo

}