Directi Interview Question
0of 0 votesfind ginen BT is BST or not?
Country: India
Interview Type: Phone Interview
bool IsBinarySearchTree(struct node * root)
{
if (NULL == root)
return true;
if (NULL != root->left && root->data < root->left->data)
return false;
if (NULL != root->right && root->data > root->right->data)
return false;
return IsBinarySearchTree(root->left) && IsBinarySearchTree(root->right);
}
public static boolean isBST ( Node root ) {
List<Integer> inOrderList = new ArrayList<Integer>();
getInorder(root, inOrderList);
int max = inOrderList.get(0);
for ( Integer element : inOrderList ) {
if ( element < max ) {
return false;
} else {
max = element;
}
}
return true;
}
private static void getInorder ( Node root, List<Integer> numberList ) {
if ( root != null ) {
getInorder(root.getLeft(), numberList);
numberList.add(root.getVal());
getInorder(root.getRight(), numberList);
}
}
@eugene: Nitpick: "You can beat O(n)" is kind of nonsensical, because BigOh denotes an upper bound...
This algorithm has O(n) space complexity.
We can have the following algorithm if we want to avoid space.
public static boolean isBSTWithNoSpace(Node root) {
if ( root != null ) {
int rootVal = root.getVal();
Node leftNode = root.getLeft();
Node rightNode = root.getRight();
// Case where the node is a leaf node
if ( leftNode == null && rightNode == null ) {
return true;
}
// Case where the node has both right and left child
if ( leftNode != null && rightNode != null ) {
if ( leftNode.getVal() < rootVal && rightNode.getVal() > rootVal ) {
return isBSTWithNoSpace(leftNode) && isBSTWithNoSpace(rightNode);
} else {
return false;
}
}
// Case where the node has only the left child
if ( leftNode != null ) {
if ( leftNode.getVal() < rootVal ) {
return isBSTWithNoSpace(leftNode);
} else {
return false;
}
}
// Case where the node has only the right child
if ( rightNode != null ) {
if ( rightNode.getVal() > rootVal ) {
return isBSTWithNoSpace(rightNode);
} else {
return false;
}
}
return false;
} else {
return false;
}
}
Sorry, for the bad method name.
@ACP Pradyuman
I am first traversing the given tree in-order and then checking if the list of integers that I obtain is in increasing order.
Time complexity - O(n) (normal traversal)
Space complexity - O(n) (storing n elements)
Another bad thing about the algorithm is it cannot break in between. It would always traverse the whole tree. Making the best, average and worst time O(n)
On the other hand, the above algorithm doesn't bother to look further if a particular sub tree doesn't exhibit the BST property.
Complete code with all inlined comments for both BST definition and algorithm:
struct Node {
Node *left;
Node *right;
int value;
};
/**
Definition of a BST and algorithm.
Given tree is considered a BST if: (1 || (2 && 3))
1. It is an empty tree;
2. All the nodes in the left subtree of any node have values less than
or equal to the given node's value && is a BST itself;
3. All the nodes in the right subtree of any node have values greater than
the given node's value && is a BST itself;
@param lbValue - the minimum allowed value of the given node
@param ubValue - the maximum allowed value of the given node
Any node should meet this constraint: lbValue <= node.value < ubValue
The value range for any node is as follows:
For any node in the left subtree of node N:
lbValue <= child.value < N.value
For any node in the right subtree of node N:
N.value < child.value <= ubValue
*/
bool IsBST(Node *node, const int& lbValue, const int& ubValue)
{
if (NULL == node)
return true;
/* Using a tail recursion here to eliminate the stack frame inflation */
return ( (IsBST(node->left, lbValue, node->value)) &&
(IsBST(node->right, node->value, ubValue)) );
}
int main ()
{
Node *root = GenerateBinaryTree(...); // code to generate a BT (not necessarily a BST)
bool bIsBST = IsBST(root, INT_MIN, INT_MAX);
return 0;
}}
bool IsBST(struct node * root) {
- Anonymous November 08, 2012static struct node* prev = NULL;
if(root)
{
if(! IsBST(root->left)
return false;
if(prev &&(prev->data > root->data)
return false;
prev = root;
return IsBST(root->root);
}
return true;
}