Bloomberg LP Interview Question
Software DevelopersCountry: United States
Interview Type: Phone Interview
I don't think this and any of the other solutions are sufficient
to make sure the BST properties are satisfied, we need to make sure all values in left subtree are smaller than the root (instead of only the left node value)
public boolean isBST(Node n) {
if (n == null) {
return true;
}
boolean checkRight = (n.right == null) ? true : (n.right.value > n.value) ? true : false;
boolean checkLeft = (n.left == null) ? true : (n.left.value < n.value) ? true : false;
return checkRight && checkLeft && isBST(n.left) && isBST(n.right);
}
I like nikamirumukmeen's solution but I didn't want to have to keep creating 2 extra temporary variables each time we validated another node although I ended up with the same problem by creating 2 bool each call. Also wasn't a fan of copying the whole object on each validate call when we could just pass a pointer.
bool IsValidBST(BTnode* rootNode)
{
return ValidateNode(rootNode);
}
bool ValidateNode(BTnode* node)
{
bool bValidLeft = true;
bool bValidRight = true;
if (node->m_pLeft != NULL)
{
if (node->m_pLeft->m_nKey < node->m_nKey)
bValidLeft = ValidateNode(node->m_pLeft);
else
return false;
}
if (bValidLeft && node->m_pRight != NULL)
{
if (node->m_pRight->m_nKey > node->m_nKey)
bValidRight = ValidateNode(node->m_pRight);
else
return false;
}
return bValidLeft && bValidRight;
}
I think your solution is not correct. comparing every node with left child and right child won't lead to the correct solution. Actually left sub tree can't have value greater than the root and the right sub tree can't have value less than the root. That's the reason you need to keep track of min and max.
bool IsBinarySearchTree(node* n)
{
if (n == null)
return True;
if (n->left == null and n->right == null)
return True;
bool checkleft = True, checkright = True;
if (n->left != null)
if (n->content < n->left->content)
return False;
else
checkleft = IsBinarySearchTree(n->left);
if (n->right != null)
if (n->content > n->lright->content)
return False;
else
checkright = IsBinarySearchTree(n->right);
return (checkleft == checkright == True)?True:False;
}
This seems to work better. I'm just doing an inorder traversal of the tree and checking if the elements are in increasing order.
bool checkTree(Node * n) {
if ( n != NULL ) {
static int previous = -2147483648;
checkTree(n->left);
if(n->data < previous){
return false;
}
else {
previous = n->data;
}
checkTree(n->right);
}
return true;
}
bool IsBST(BTnode* node)
{
if ( node == 0 )
return true;
if (node->m_left != NULL)
{
if (node->m_left->m_key > node->m_key)
return false;
if ( !IsBST(node->m_left) )
return false;
}
if (node->m_right != NULL)
{
if (node->m_right->m_key < node->m_key)
return false;
if ( !IsBST(node->m_right) )
return false;
}
return true;
}
bool isBinarySearchTree(TreeNode* root) {
return (root->left != nullptr ? root->left->val < root->val : true)
&& (root->right != nullptr ? root->right->val > root->val : true)
&& (root->left != nullptr ? isBinarySearchTree(root->left) : true)
&& (root->right != nullptr ? isBinarySearchTree(root->right) : true);
}
bool isBinarySearchTree(TreeNode* root) {
return (root->left != nullptr ? root->left->val < root->val : true)
&& (root->right != nullptr ? root->right->val > root->val : true)
&& (root->left != nullptr ? isBinarySearchTree(root->left) : true)
&& (root->right != nullptr ? isBinarySearchTree(root->right) : true);
}
bool isBinarySearchTree(TreeNode* root) {
return (root->left != nullptr ? root->left->val < root->val : true)
&& (root->right != nullptr ? root->right->val > root->val : true)
&& (root->left != nullptr ? isBinarySearchTree(root->left) : true)
&& (root->right != nullptr ? isBinarySearchTree(root->right) : true);
}
#include <limits>
struct bt_node
{
int value;
bt_node *left, *right;
};
static bool check_bst_left(bt_node *bt, int parent_value, int lbound, int rbound);
static bool check_bst_right(bt_node *bt, int parent_value, int lbound, int rbound);
bool check_bst(bt_node *bt, bt_node *parent)
{
return check_bst_left(bt->left, bt->value, std::numeric_limits<int>::min(), bt->value)
&& check_bst_right(bt->right, bt->value, bt->value, std::numeric_limits<int>::max());
}
static bool check_bst_left(bt_node *bt, int parent_value, int lbound, int rbound)
{
if (!bt)
return true;
return bt->value >= lbound && bt->value <= parent_value
&& check_bst_left(bt->left, bt->value, lbound, bt->value)
&& check_bst_right(bt->right, bt->value, bt->value, rbound);
}
static bool check_bst_right(bt_node *bt, int parent_value, int lbound, int rbound)
{
if (!bt)
return true;
return bt->value >= parent_value && bt->value <= rbound
&& check_bst_left(bt->left, bt->value, lbound, bt->value)
&& check_bst_right(bt->right, bt->value, bt->value, rbound);
}
bool checkBST(treeNode* n){
vector<int> cache;
inOrderTraverse(n);
int last = *cache.begin()
for(auto it=cache.begin()+1; it!=cache.end(); it++){
if (*it < last){ return false; }
}
return true;
}
void inOrderTraverse(treeNode* n, vector<int> &cache){
if(n==NULL){ return ;}
inOrderTraverse(n->Left, cache);
visitNode(n, cache);
inOrderTraverse(n->Right, cache);
}
void visitNode(treeNode* n, vector<int> &cache){
cache.push_back(n->data);
}
In Order Traversal with data saved from last and current
static int prev = 0;
static int curr = 0;
public static boolean IsValidBST(BinaryTree root){
if (root == null)
return true;
if(!IsValidBST(root.left))
return false;
prev = curr;
curr = root.data;
if(prev >= curr){
System.out.println("Not a BST Tree");
return false;
}
if(!IsValidBST(root.right))
return false;
return true;
}
You can always do in order traversal and save current and prev value..
static int prev = 0;
static int curr = 0;
public static boolean IsValidBST(BinaryTree root){
if (root == null)
return true;
if(!IsValidBST(root.left))
return false;
prev = curr;
curr = root.data;
if(prev >= curr){
System.out.println("Not a BST Tree");
return false;
}
if(!IsValidBST(root.right))
return false;
return true;
}
static int prev = 0;
static int curr = 0;
public static boolean IsValidBST(BinaryTree root){
if (root == null)
return true;
if(!IsValidBST(root.left))
return false;
prev = curr;
curr = root.data;
if(prev >= curr){
System.out.println("Not a BST Tree");
return false;
}
if(!IsValidBST(root.right))
return false;
return true;
}
{{
private static boolean ans = true;
public boolean isValidBST(TreeNode root) {
if(root == null) return true;
ans = true;
solve(root);
return ans;
}
private void solve(TreeNode root) {
if(root == null) return;
dfs(root.left, root.val, -1);
dfs(root.right, root.val, 1);
solve(root.left);
solve(root.right);
}
void dfs(TreeNode node, int val, int p) {
if(node == null) return;
if(p==-1 && node.val >= val){
ans = false;
return;
}
else if(p==1 && node.val <= val) {
ans = false;
return;
}
dfs(node.left, val, p);
dfs(node.right, val, p);
}
}}
- nikamirulmukmeen March 19, 2015