3.2.32 Certification. Write a method isBST() that takes a Node as argument and r

Question

3.2.32 Certification. Write a method isBST() that takes a Node as argument and returns
true if the argument node is the root of a binary search tree, false otherwise.
Hint : This task is also more difficult than it might seem, because the order in which you
call the methods in the previous three exercises is important.

Solution :
private boolean isBST()
{
if (!isBinaryTree(root)) return false;
if (!isOrdered(root, min(), max())) return false;
if (!hasNoDuplicates(root)) return false;
return true;
}

Explanation / Answer

class Node
{
int data;
Node left, right;

public Node(int item)
{
data = item;
left = right = null;
}
}

public class BinaryTree
{
Node root;

boolean isBST() {
return isBSTcheck(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}

boolean isBSTcheck(Node node, int min, int max)
{
if (node == null)
return true;

if (node.data < min || node.data > max)
return false;

return (isBSTcheck(node.left, min, node.data-1) &&
isBSTcheck(node.right, node.data+1, max));
}

public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(4);
tree.root.left = new Node(2);
tree.root.right = new Node(5);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(3);

if (tree.isBST())
System.out.println("IS BST");
else
System.out.println("Not a BST");
}
}

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.