Interview Question
Country: United States
/* check for BST */
private static boolean isBST(BSTNode root) {
if (root == null)
return true;
if (root.getLeft() != null && findMax(root.getLeft()) > root.getData())
return false;
if (root.getRight() != null
&& findMin(root.getRight()) < root.getData())
return false;
if (!(isBST(root.getLeft())) || (!isBST(root.getRight())))
return false;
return true;
}
Inorder traversal is also a nice solution. I will try to explain the algorithm without using any auxiliary array.
Let prev = -INFINITY;
//function to check if tree is BST
boolean traverse(Node *n){
if(node n is NULL) return true;
else if node n is a leaf and prev <= n {
prev = n;
return true;
}
boolean flag = false, leftFlag = false, rightFlag = false;
leftFlag = traverse(n.left); //check left subtree
if(prev <= n.key) {
prev = n.key;
flag = true;
}
rightFlag = traverse(n.right); //check right subtree
return (leftFlag && flag && rightFlag);
}
Following is the pseudocode:
Triplet {
boolean isBST; //The tree is BST or not
int min; //Minimum value in the tree
int max; //Maximum value in the tree
}
//check if subtree rooted at "root" is a BST
Triplet checkBST(Node root) {
Triplet leftT, rightT;
//IGNORING BOUNDARY CASES LIKE LEAVES ...
leftT = checkBST(root.left);
rightT = checkBST(root.right);
//if both left and right subtrees are BSTs
if(leftT.isBST && rightT.isBST) {
//if this node is following the BST property then
if(leftT.max<=root.key && root.key<=rightT.min)
//the subtree rooted at this node is BST
return new Triplet(true, leftT.min, rightT.max);
}
return new Triplet(false, leftT.min, rightT.max); //not a BST
}
void check(sn *start){
sn * prev;
if(start != NULL){
prev = start;
check(start->left)
if(prev -> data > start -> data)
printf("The no = %d\n",start -> data);
else{
printf("It is not bst\n");
exit(0);
}
check(start -> right);
else
return;
}
The following code is O(n). The concept is that if every node in the tree is a BST Node, then the tree is a BST. Basically if the node has a left or right child, you need to make sure
1) That the left child is smaller than it, and the right child is larger than it
2) that the left and right children are also binary search tree nodes
As soon as a condition doesn't apply you should return false. In the second if statement I could reduce some redundancy of only checking the left node if the right node was a BST node.
bool isBST(Node root)
{
bool isBSNode = true;
if (root == null)
return isBSNode;
if (root.Right != null)
{
if (root.Value >= root.Right.Value)
return false;
isBSNode = isBSNode && isBST(root.Right);
}
if (root.Left != null)
{
if (root.Value <= root.Left.Value)
return false;
isBSNode = isBSNode && isBST(root.Left);
}
return isBSNode;
}
Actually I could save some complexity by doing the following
if (root.Right != null)
{
if (root.Value >= root.Right.Value)
return false;
isBSNode = isBST(root.Right);
}
if (isBSNode && root.Left != null)
{
if (root.Value <= root.Left.Value)
return false;
isBSNode = isBST(root.Left);
}
Doing a preorder traversal of the tree would give a fail-fast result. It means stop traversing the tree as soon as a node is found not to comply with BST.
public boolean isBST(Node root) {
if(root==null) return true;
return (root.left==null || root.value >= root.left) // Check current node with left node
&& (root.right==null || root.value <= root.right ) // Check current node with right node
&& isBST(root.left) && isBST(root.right);
}
There is mistake in the solution. If root node is greater than or equal to left node and smaller than or equal to right node and both left node and right node it self is BST then also it is possible that it's not a valid bst. You need to add a condition and need to check it recursively that root node is always greater than or equal to Max(root-->left) and less than or equal to Min(root-->right)
here is the java implementation of this
public boolean isBST(BinaryNode node)
{
boolean isBst = true;
if (node == null)
{
return true;
}
if(node.left != null)
{
isBst = (node.data >= node.left.data) && (node.data >= max(node.left).data) && (isBST(node.left));
}
if(isBst && node.right != null)
{
isBst = (node.data <= node.right.data) && (node.data <= min(node.right).data) && (isBST(node.right));
}
return isBst;
}
private boolean isBSTAlternative(Node node, NodeHolder lastNode)
{
if (node == null)
return true;
if (isBSTAlternative(node.left, lastNode))
{
if (lastNode.node != null) {
if (lastNode.node.data > node.data)
return false;
}
lastNode.node = node;
return isBSTAlternative(node.right, lastNode);
}
return false;
}
public boolean BST(Tree root){
boolean flag;
if(root.value){
return true;
} else if(root.getLeft().value<root.value && root.getRigth().value>root.value){
flag = BST (root.getLeft());
if(flag==true){
flag = BST(root.getRigth());
} else {
return flag;
}
} else {
return false;
}
return flag;
}
public boolean BST(Tree root){
boolean flag;
if(root.value){
return true;
} else if(root.getLeft().value<root.value && root.getRigth().value>root.value){
flag = BST (root.getLeft());
if(flag==true){
flag = BST(root.getRigth());
} else {
return flag;
}
} else {
return false;
}
return flag;
}
java:
public boolean isBST(TreeNode root){
return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
isBST(TreeNode root, int min, int max){
if(root==null)
return true;
if(root.val>=min&&root.val<max){
return isBST(root.left, min, root.val)&&isBST(root.right, root.val, max);
}
else return false;
}
Correct solution is
1) root.data >= root-->left.data and root.data >= Max(root-->left) and root--left is BST
2) root.data <= root-->right.data and root.data <= Min(root-->right) and root-->right is BST
public boolean isBST(BinaryNode node)
{
boolean isBst = true;
if (node == null)
{
return true;
}
if(node.left != null)
{
isBst = (node.data >= node.left.data) && (node.data >= max(node.left).data) && (isBST(node.left));
}
if(isBst && node.right != null)
{
isBst = (node.data <= node.right.data) && (node.data <= min(node.right).data) && (isBST(node.right));
}
return isBst;
}
public BinaryNode min(BinaryNode node)
{
if(node == null)
{
return node;
}
if (node.left == null)
{
return node;
}
else
{
return min(node.left);
}
}
public BinaryNode max(BinaryNode node)
{
if (node.right == null)
{
return node;
}
else
{
return max(node.right);
}
}
- Vir Pratap Uttam May 05, 2015