Question: 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
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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help