## Twitter Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

```
public boolean isBST(TreeNode root, int min,int max)
{
if(root==null)
return true;
if(root.value<min||root.value>max)
return false;
return isBST(root.left,min,root.value)&&isBST(root.right,root.value,max)
}
First call will be isBST(root,INT.min,INT.max);
```

@Anonymous Your code returns true if the root and its left node have the same value. BST elements are unique.

There are 3 solutions using DFS, BFS, and Morris traversal to detect a binary tree is a BST or not at the entry "Does a binary tree satisfy the BST property?" of code.google.com/p/elements-of-programming-interviews/wiki/Programs

It is the solutions of another programming interviews book titled "Elements of Programming Interviews: 300 Questions and Solutions"

4 lines with recursion. i hope i'm not missing something here.. this should work

```
public boolean isBST(Node n){
if(n == null || ((n.right == null) && (n.left == null))) return true; //child node or base case
if((n.left == null || n.right == null) && (n.left.value > n.value || n.right.value < n.value) return false; //unbalanced tree
if(n.left.value > n.right.value) return false;// not correct bst
return isBST(n.left) && isBST(n.right); //check all nodes
}
```

{{

struct node

{

int data;

struct node *next;

}*start;

void Check_Bst(node root)

{

Check_Bst(root->left);

linkedlist(root);

Check_Bst(root->right);

}

void linkedlist(node root)

{

struct node *new , temp;

new =(struct node*)malloc(sizeof(struct node));

new->data = root->data;

new->next=NULL;

if(start ==NULL)

start=new;

else

{

temp=start;

while(temp->next!=NULL)

temp=temp->next;

temp->next=new;

}

}

void display(struct node *root)

{

struct node *flow;

flow=root->next;

if(root==NULL)return 0;

else

{

while(root!=NULL)

{

if(flow->data >root->data)

{

root=flow;

flow=flow->next;

}

else

{

flag=0;

break;

}

}

}

if(flag==0)

printf("not BST");

}

void main()

{

Check_Bst(root);

display(root);

}

}}

Why not Level order Traversal?

Refer :

www[dot]geeksforgeeks[dot]org/level-order-tree-traversal/

Little modification needed as below :

boolean isBST(root) {

int rear, front;

struct node **queue = createQueue(&front, &rear);

struct node *temp_node = root;

while(temp_node) {

//printf("%d ", temp_node->data);

/*Enqueue left child */

if(temp_node->left && temp_node->left < data) {

enQueue(queue, &rear, temp_node->left);

} else {

return false ;

}

/*Enqueue right child */

if(temp_node->right && temp_node->right->data > data ) {

enQueue(queue, &rear, temp_node->right);

} else {

return false ;

}

/*Dequeue node and make it temp_node*/

temp_node = deQueue(queue, &front);

}

//All the nodes are passed

return true;

}

1.) Do inorder traversal of the tree

2.)check whethr the obtained list is in Ascending or Descending Order as per requirement

;)

Given that TreeNode has a left and right nodes and a payload that implements Comparable.

```
public boolean checkBST(TreeNode<T> root) {
if(root==null) return true;
T payload = root.getPayload();
if ((root.left!=null && root.left.getPayload().compareTo(payload)>0) || (root.right!=null && root.right.getPayload().compareTo(payload)<0)) {
return false;
} else {
return checkBST(root.left) && checkBST(root.right);
}
}
```

Perform an inorder traversal, it should result in an increasing order of elements!

- Mk January 23, 2013