Microsoft Interview Question Software Engineer in Tests
Country: United States
Yes I agree to that.. Also we can keep a variable as a flag so that we dont recursively check the value of every node in inorder traversal.. once we find out that a particular node is not in sorted order
for your solution, there need extra space to store the list. if no extra space, how to make it?
Here is an intelligent algo I have seen somewhere in the net.
As you navigate down the tree, narrow the min and max conditions based on current node. Left should be always less than current node. And right should be greater.
public static boolean isBinaryTree(BinaryTreeNode node, int min, int max)
{
boolean returnBool = false;
if(node.data >= min || node.data <= max)
returnBool = true;
if(node.left != null)
returnBool = returnBool && isBinaryTree(node.left, min, node.data - 1);
if(node.right != null)
returnBool = returnBool && isBinaryTree(node.right, node.data + 1, max);
return returnBool;
}
On similar lines...
public static boolean inorderTraversal(BinaryTreeNode node)
{
bool returnBool = true;
if(node != null)
{
if(node.left != null) {
if(node.value > node.left.value)
returnBool = returnBool && inorderTraversal(node.left);
else
return false;
}
if(node.right != null) {
if(node.value <= node.right.value)
returnBool = returnBool && inorderTraversal(node.right);
else
return false;
}
}
return returnBool;
}
bool IsTreeBST(TreeNode * root)
{
if (NULL != root->left)
{
if (root->left->value > root->value)
return false;
return IsTreeBST(root->left);
}
if (NULL != root->right)
{
if (root->right->value <= root->value)
return false;
return IsTreeBST(root->right);
}
return true;
}
class TreeNode
{
public:
int value;
TreeNode * left;
TreeNode * right;
};
This algo will return true for
10
8 12
6 14 2 18
But this is not a binary search tree. The problem being that all the nodes in left should be smaller than root node and not just the immediate left child. Similarly all the nodes in right should be larger than root node and not just the immediate right child
static bool IsItBST(Node root)
{
if (root == null) return true;
if (root.left == null)
{
if (root.right == null) return true;
else if (root.right.data < root.data) return false;
}
else
{
if (root.left.data > root.data) return false;
if (root.right == null) return true;
if (root.right.data < root.data) return false;
}
if (!IsItBST(root.left)) return false;
if (!IsItBST(root.right)) return false;
return true;
}
bool isValidBST(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//if (root == NULL) return true;
return isValid(root, -1*INT_MAX, INT_MAX);
}
bool isValid(TreeNode *root, int min, int max){
if (root == NULL) return true;
if (root->val <= min || root->val >= max) return false;
if (root->left) {
if (root->val < root->left->val) return false;
}
if (root->right) {
if (root->val > root->right->val) return false;
}
bool ret = true;
ret &= isValid(root->left, min, root->val);
ret &= isValid(root->right, root->val, max);
}
// took from leetcode
bool isValidBST(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//if (root == NULL) return true;
return isValid(root, -1*INT_MAX, INT_MAX);
}
bool isValid(TreeNode *root, int min, int max){
if (root == NULL) return true;
if (root->val <= min || root->val >= max) return false;
if (root->left) {
if (root->val < root->left->val) return false;
}
if (root->right) {
if (root->val > root->right->val) return false;
}
bool ret = true;
ret &= isValid(root->left, min, root->val);
ret &= isValid(root->right, root->val, max);
}
If you do this recursively, this only need one line, and time complexity is O(n).
class Node {
public:
int value;
Node *left, *right;
};
bool checkBST(Node *root) {
return (root == NULL) ||
((root->left == NULL || root->left->value <= root->value) &&
(root->right == NULL || root->value <= root->right->value) &&
checkBST(root->left) && checkBST(root->right));
}
#include<iostream>
using namespace std;
/*
How to check if a binary tree is a binary search tree
*/
typedef struct node_s {
int value;
struct node_s *left;
struct node_s *right;
}BSTNode, *BSTree;
int tree_search(BSTree T, int value, BSTNode **p, BSTNode *f) {
if(!T) {
*p = f;
return 0;
} else {
if(T->value == value) {
*p = T;
return 1;
} else if(value < T->value) {
return tree_search(T->left, value, p, T);
} else {
return tree_search(T->right, value, p, T);
}
}
}
int tree_insert(BSTree *T, int value) {
BSTNode *p = NULL;
if(!tree_search(*T, value, &p, NULL)) {
BSTNode *s = (BSTNode*)malloc(sizeof(BSTNode));
s->value = value;
s->left = NULL;
s->right = NULL;
if(!(*T))
*T = s;
else if(value < p->value)
p->left = s;
else
p->right = s;
return 1;
}
return 0;
}
bool is_bst = true;
void check_tree_is_bst(BSTree T) {
if(T) {
check_tree_is_bst(T->left);
if(T->left) {
if(T->left->value > T->value) {
is_bst = false;
return;
}
}
if(T->right) {
if(T->right->value < T->value) {
is_bst = false;
return;
}
}
check_tree_is_bst(T->right);
}
}
int main(int argc, char *argv[]) {
int a[] = {5, 9, 13, 4, 6, 7, 34, 12, 25, 16};
int len = sizeof(a) / sizeof(int);
int i;
BSTree T = NULL;
for(i = 0; i < len; i++)
tree_insert(&T, a[i]);
check_tree_is_bst(T);
if(is_bst)
cout << "yes" << endl;
else
cout << "no" << endl;
return 0;
}
#include<stdio.h>
struct bst
{
int data;
struct bst *left;
struct bst *right;
};
typedef struct bst node;
node *buildtree(int val,node *parent,int flag)
{
node *ptr=(node*)malloc(sizeof(node));
ptr->data=val;
ptr->left=NULL;
ptr->right=NULL;
if(flag==1)
{
parent->left=ptr;
}
else if(flag==2)
{
parent->right=ptr;
}
return ptr;
}
node *inorder(node *ptr)
{
node *ptr1=ptr;
if(ptr1==NULL)
return NULL;
inorder(ptr1->left);
printf("%d ",ptr1->data);
inorder(ptr1->right);
}
int isbst(node *hptr)
{
int max=0;
max=hptr->data;
if(hptr==NULL)
return 0;
if(hptr->left==NULL)
return 0;
if(hptr->right==NULL)
return 0;
else if(max>hptr->left->data && max<hptr->right->data);
{
isbst(hptr->left);
isbst(hptr->right);
}
else
return 0;
}
int main()
{
int x;
node *a1,*b1,*e1,*f1,*c1,*d1,*a,*b,*c,*d,*e,*f,*ptr,*ptr1,*root1,*ptr2;
node *root=(node*)malloc(sizeof(node));
root1=(node*)malloc(sizeof(node));
ptr=root;
root->data=10;
root->left=NULL;
root->right=NULL;
a=buildtree(200,root,1);
b=buildtree(300,root,2);
c=buildtree(250,a,1);
d=buildtree(310,a,2);
e=buildtree(410,b,1);
f=buildtree(450,b,2);
printf("first tree:");
//inorder(ptr);
x=isbst(ptr);
if(x)
printf("yes");
else
printf("no");
}
#include<stdio.h>
#include<stdio.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node* createnode(int ch,struct node *parent,int flag)
{
struct node *nptr;
nptr=(struct node*)malloc(sizeof(struct node));
nptr->data=ch;
nptr->left=nptr->right=NULL;
if(flag==1)
{
parent->left=nptr;
}
else
parent->right=nptr;
return nptr;
}
void inorder( struct node * root)
{//printf("hiihihi");
if(root==NULL)
return;
inorder(root->left);
printf("%d\n",root->data);
inorder(root->right);
}
int isBSTHelper(struct node *p, int low, int high) {
printf("max :%d min:%d\n",high,low);
if(p==NULL)
return 1;
if (low < p->data && p->data < high)
return (isBSTHelper(p->left, low, p->data) &&
isBSTHelper(p->right, p->data, high));
else
return 0;
}
int isBST(struct node *root) {
return isBSTHelper(root, -1, 999999);
}
int main()
{ int m;
struct node *root,*p1,*p2,*p3,*p4,*p5,*p6,*p7,*p8,*p9,*p10,*p11;
struct node *iptr,*j,*d;
root=(struct node*)malloc(sizeof(struct node));
root->data=5;
root->left=root->right=NULL;
p1=createnode(2,root,1);
p8=createnode(15,root,2);
p2=createnode(1,p1,1);
p3=createnode(4,p1,2);
p4=createnode(14,p8,1);
p5=createnode(17,p8,2);
j=root;
iptr=root;
inorder(iptr);
m=isBST(j);
if(m)
printf("it is bst");
else
printf("it is not bst");
}
o(1) space and O(n) time complexity.
Every node visited once.
#include<iostream>
#include <limits.h>
using namespace std;
/* A binary tree node has
data,
pointer to left child
pointer to right child
*/
struct node
{
int data;
struct node* left;
struct node* right;
};
typedef struct node Node;
/* Function that allocates a new node with the
given data and sets up left and right pointers as NULL value.
*/
Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
//------------------------------------code here----------------------
//Function that checks if given tree is a BST. Declared here.
bool isBST_Full(Node *p, int& prev);
//Helper function for easy use. Sets up a buffer that is needed by the code
bool isBST(Node *p)
{
int prev = numeric_limits<int>::min(); // minimum value held in int
return(isBST_Full(p, prev));
}
bool isBST_Full(Node *p, int& prev)
{
if(!p) return true;
if(isBST_Full(p->left,prev))
{
if(p->data>=prev)
{
prev = p->data;
return(isBST_Full(p->right,prev));
}
else return false;
}
else return false;
}
//----------------------------------------------------------------------------
int main()
{
struct node *root = newNode(4);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);
root->right->right = newNode(8);
if(isBST(root))
printf("Is BST");
else
printf("Not a BST");
return 0;
}
//Check the tree inorder and see if that is in ascending order
//Helper function for easy use. Sets up a buffer that is needed by the code
bool bst(Node *p)
{
int buf_min = numeric_limits<int>::min(); // minimum value held in int
return(bst_full(p, buf_min));
}
//Code that checks if the tree is a BST
bool bst_full(Node *p, int& buf_min)
{
if(!p) return true;
if(bst_full(p->left,buf_min))
{
if(p->data >= buf_min)
{
buf_min = p->data;
return bst_full(p->right,buf_min);
}
else return false;
}
else return false;
}
This is another recursive approach but does not use any min max variables.
The approach is
1. Figure out if the current node is following BST rule which is left.data <= root.data <= right.data
2. Now do this for left child and right child and return the result of steps 1 & 2
public boolean isBST(TreeElement root) {
if (root == null || (root.left == null && root.right == null)) {
return true;
}
boolean result = true;
if ((root.left != null && root.left.data > root.data)
|| (root.right != null && root.right.data < root.data)) {
result = false;
}
return result && isBST(root.left) && isBST(root.right);
}
bool isBST(struct node* root) {
if(root == NULL)
return true;
if(root->left && root->data < max(root->left)) {
return false;
}
if(root->right && root->data >= min(root->right)) {
return false;
}
return isBST(root->left) && isBST(root->right);
}
int max(struct node* root) {
if(root == NULL) {
return -1;
}
while(root->right) {
root = root->right;
}
return root->data;
}
int min(struct node* root) {
if(root == NULL) {
return -1;
}
while(root->left) {
root = root->left;
}
return root->data;
}
int isbst (struct tree *root) {
if (root == NULL)
return 1;
if (root->left == NULL &&
root->right == NULL)
return 1;
else if (root->left == NULL) {
if (root->data < root->right->data)
return isbst(root->right);
else
return 0;
} else if (root->right == NULL) {
if (root->data >= root->left->data)
return isbst(root->left);
else
return 0;
} else {
if (root->data < root->right->data &&
root->data >= root->left->data)
return (isbst(root->left &&
isbst(root->right));
else
return 0;
}
}
I think this is simple, just use the defination of bst that the data of the root is smaller than the data stored in its left child if there is left child, and the same the data store in its rigth child is larger than the data of root, then check this recursively and finally you will get the result, here are my codes, if there is anything wrong, please let me know, thank you!
#include<iostream>
using namespace std;
typedef struct tree_node_s {
int data;
struct tree_node_s* lchild;
struct tree_node_s* rchild;
}tree_node_t;
tree_node_t* createNode(int data) {
tree_node_t* node = (tree_node_t*)malloc(sizeof(tree_node_t));
node->data = data;
node->lchild = NULL;
node->rchild = NULL;
return node;
}
bool isBST(tree_node_t* root) {
if (NULL == root)
return true;
bool left = true;
bool right = true;
if (root->lchild) {
if (root->data > root->lchild->data) {
left &= isBST(root->lchild);
} else {
return false;
}
}
if (root->rchild) {
if (root->data < root->rchild->data) {
right &= isBST(root->rchild);
} else {
return false;
}
}
return left & right;
}
int main(int argc, char* argv[]) {
tree_node_t* root = createNode(10);
root->lchild = createNode(7);
root->rchild = createNode(19);
root->lchild->lchild = createNode(4);
root->lchild->rchild = createNode(8);
root->rchild->lchild = createNode(13);
root->rchild->rchild = createNode(21);
if (isBST(root))
cout << "yes" << endl;
else
cout << "non" << endl;
cin.get();
return 0;
}
bool ifbtreeisbst(treenode* root, int & flag)
{
if(!root)
return false;
if((root->left && (root->left->data > root->data)) || (root->right && (root->right->data < root->data)))
flag=1;
if(flag==1)
{
return false;
}
else
{
ifbtreeisbst(root->left,flag);
ifbtreeisbst(root->right, flag);
}
return true;
}
You simply take the inorder traversal of the binary tree and check if it is sorted. If yes it is a binary search tree else no.
- Expressions March 26, 2013