Microsoft Interview Question
Software Engineer InternsCountry: United States
Interview Type: Written Test
def IsBST(tree):
if tree == None:
return True, None, None
left, left_min, left_max = IsBST(tree.left)
if not left or tree.value < left_max:
return False, min(left_min, tree.value), max(left_max, tree.value)
right, right_min, right_max = IsBST(tree.right)
if not right or tree.value > right_min:
return False, min(left_min, tree.value), max(tree.value, right_max)
return True, min(left_min, tree.value), max(right_max, tree.value)
Most of the answers are wrong. As @msft pointed out the solutions will return the following BST is valid
5 <- 10 ->15
Left child of 5 is 20. This is not a BST but the solutions would validate this case..
The simplest solution is to perform inorder traversal and check if every node is greater than the previous node. If the inorder traversal is sorted then it is a BST.
int isBST(struct node* node) {
return(checkIsBST(node, INT_MIN, INT_MAX));
}
int checkIsBST(struct node* node, int min, int max) {
if (node==NULL)
return true;
if (node->data<min || node->data>max)
return false;
return
( checkIsBST(node->left, min, node->data) &&
checkIsBST(node->right, node->data+1, max) );
}
One has to make a mistake once in their life to get the small trap in this problem.
If you have not coded this ever, you will most likely come up with (in nervous interview) checking that every left child is less than and ever right child is greater than current node (then recurse to children).
But we have to check that WHOLE left subtree is less than and WHOLE right subtree is greater than.
Basically google you should question and study the pitfalls and the correct inefficient and efficient solutions.
You can't judge hiring methods based on just one question. This might be more of a coding question etc.
Anyways, you are right though.
Microsoft needs to improve, not just in their hiring methods.
Still trying to understand what you meant here. If we check
Note: We will check if root/left/right node is not null every time.
1) LeftChild is less than root
2) RightChild is greater than root
3) Apply recursive way for bot left and right subtree(which will be passing leaft and right node again following same pattern)
why it will be incorrect solution? Can you help me here?
@NewUser
consider a situation where the root node is 5 - its left child is 3 - right child of the left one is 6.
. 5
. / \
3
./\
6
and your code checks if the right node is greater than its parent which is true in ur case and so you will return true for binary tree integrity
do u get the point?
I guess according to msft we are supposed to start comparing bottom up and not top down
I didn't test it. hope It works
public static void isValidBST(Node node,int minValue, int maxValue)
{
if(node == null)
{
return true;
}else
{ if(node.value < minValue && node.value > maxValue)
{
return false;
}
return isValidBST(node.left,minValue,node.value) && isValidBST(node.right,node.value,maxValue);
}
}
It seams you wanted to write OR instead of AND:
if(node.value < minValue || node.value > maxValue)
If the values stored at tree are ints then we can set inital min/maxValues by INT_MIN and INT_MAX values. Else we should add two flags minValueSet, maxValueSet and improve the condition when the false value is returned
C++ version.
#include <iostream>
#include <limits>
template <typename T>
struct bst_node {
bst_node() : left_(nullptr), right_(nullptr), data_() { }
bst_node(const T& data) : left_(nullptr), right_(nullptr), data_(data) { }
~bst_node() { delete left_; delete right_; }
bst_node *left_;
bst_node *right_;
T data_;
};
template <typename T>
bool is_valid_bst_r(const bst_node<T>* root, const bst_node<T>*& prev) {
if (!root)
return true;
if (!is_valid_bst_r(root->left_, prev))
return false;
if (prev && root->data_ <= prev->data_)
return false;
prev = root;
return is_valid_bst_r(root->right_, prev);
}
template <typename T>
bool is_valid_bst(const bst_node<T>& root) {
const bst_node<T>* prev = nullptr;
return is_valid_bst_r(&root, prev);
}
int main() {
std::cout << std::boolalpha;
bst_node<int> root(5);
root.left_ = new bst_node<int>(4);
root.right_ = new bst_node<int>(6);
root.left_->left_ = new bst_node<int>(1);
//root.right_->left_ = new bst_node<int>(3);
std::cout << is_valid_bst(root) << std::endl;
return 0;
}
What if T is a custom type with just a compare function? Don't think std::numeric_limits will work.
If you want to make this generic. Make it truly generic.
One possible way: Write a wrapper around T, which has two boolean flags min and max and the compare function of the wrapper looks at those flags.
1. Check to see if the node is greater than or equal to max value of the left subtree
2. Check to see if the node is less than the minvalue of the right subtree
3. Check to see if the left or right subtrees are invalid
4. if all tests pass, then return true
template <class T>
bool validateBST(BinaryNode<T> *node){
if(node == NULL){
return true;
}
//If the max value of the left subtree is bigger than the node return false
//If the min value of the right subtree is smaller than the node return false
if(node->right != NULL && node->data < maxValue(node->right) ||
node->left != NULL && node->data >= minValue(node->left))
{
return false;
}
//check if either of the trees are invalid
//if any subtree is invalid, return false
if(!validateBST(node->left) || !validateBST(node->right)){
return false;
}
//we passed all the tests, so its valid :)
return true;
}
//Caller must make sure to not pass a NULL node
template <class T>
int maxValue(BinaryNode<T> *node){
//Recursively traverse down to the right node
//When we're at the current node, check if it's right child is null
//if the right child is null, then that means were the max
return (node->right == NULL) ? node->data : maxValue(node->right);
}
//Caller must make sure to not pass a NULL node
template <class T>
int minValue(BinaryNode<T> *node){
//Recursively traverse down to the left node
//When we're at the current node, check if it's left child is null
//if the left child is null, then that means the current node is the min
return (node->left == NULL) ? node->data : minValue(node->left);
}
static int Pre = INT_MIN;
bool IsValidBST(root)
{
Pre = INT_MIN;
return IsValidBST(root)
}
bool Verify(TreeNode* root)
{
if( !root ) return true;
if( !Verify(root->left) ) return false;
if( root->data < Pre ) return false;
Pre = root->data;
if( !Verify(root->left) ) return false;
return true;
}
What you guys think about this?
boolean isBST(node root)
{
if(root==null) return true;
if((root->left !=null && root->left->data > root->data) ||
(root->right !=null && root->right->data < root->data) )
return false;
return isBST(root-left) && isBST(root->right);
}
Hey, it doesn't work. as it aways return true because of first condition. Look for solution below.
Thanks Mallan for your input. Below is corrected code. I like your solution, except I don't want to pass additional parameter. Please let me know if you see any issue.
bool isBST(Node root)
{
if(node==null) return true;
if(node->left !=null && node->left->data > node->data) return false;
if(node->right!=null && node->right->data < node->data) return false;
if(!isBSTR(root->left) || !isBST(root->right) return false;
return true;
}
Why not just push the root node into a stack, say stack A. Then, until A is empty, pop A into some node variable n, validate that n->left is less than n->value and n->right is greater than n->value. If both are true, push n->right then push n->left. Else, return false. If A becomes empty, return true.
struct Node
{
int val;
Node* left;
Node* right;
};
bool checkIntegrityRec(Node* node, int& prevVal)
{
if (!node)
return true;
if (!checkIntegrityRec(node->left, prevVal))
return false;
if (node->val < prevVal)
return false;
prevVal = node->val;
if (!checkIntegrityRec(node->right, prevVal))
return false;
return true;
}
bool checkIntegrity(Node* root)
{
Node* n = root;
while (n->left)
n = n->left;
int prevVal = n->val - 1;
return checkIntegrityRec(root, prevVal);
}
public boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isValidBSTHelper(TreeNode node, int minValue, int maxValue) {
if (node == null) {
return true;
}
if (node.val > minValue && node.val < maxValue) {
return isValidBSTHelper(node.left, minValue, node.val) && isValidBSTHelper(node.right, node.val, maxValue);
} else {
return false;
}
}
public boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isValidBSTHelper(TreeNode node, int minValue, int maxValue) {
if (node == null) {
return true;
}
if (node.val > minValue && node.val < maxValue) {
return isValidBSTHelper(node.left, minValue, node.val) && isValidBSTHelper(node.right, node.val, maxValue);
} else {
return false;
}
}
public boolean isValidBST(TreeNode root) {
return isValidBSTHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isValidBSTHelper(TreeNode node, int minValue, int maxValue) {
if (node == null) {
return true;
}
if (node.val > minValue && node.val < maxValue) {
return isValidBSTHelper(node.left, minValue, node.val) && isValidBSTHelper(node.right, node.val, maxValue);
} else {
return false;
}
}
Got this question on Outlook Desktop team interview. The extra challenge was that duplicates are allowed and they should be on the left from parent - 5 < 5 > 10 is valid, but 4 < 5 > 5 is not. Here's solution (using inorder traversal)
typedef struct BinaryTree
{
struct BinaryTree *Left;
struct BinaryTree *Right;
int Data;
} BTree, *PBTree;
bool IsBinaryTreeBST(PBTree root, PBTree *prev)
{
bool fBSTTree = true;
if (root && prev)
{
if (root->Right && root->Right->Data == root->Data)
{
fBSTTree = false;
}
if (fBSTTree)
{
fBSTTree = IsBinaryTreeBST(root->Left, prev);
if (fBSTTree)
{
if (*prev && (*prev)->Data > root->Data)
{
fBSTTree = false;
}
*prev = root;
if (fBSTTree)
{
fBSTTree = IsBinaryTreeBST(root->Right, prev);
}
}
}
}
return fBSTTree;
}
void IsBST(Node* current,bool& isBST)
{
if(current == 0 || isBST == false) return;
if(current->Left != NULL && current->Left->Data > current->Data)
{
isBST = false;
return;
}
if(current->Right!= NULL && current->Right->Data < current->Data)
{
isBST = false;
return;
}
IsBST(current->Left,isBST);
IsBST(current->Right,isBST);
}
Pythonic version
- Anonymous November 29, 2013