## Twitter Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 11 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

elegant and simple! However we can terminate the search earlier if we found the element's value starts to decrease.

Comment hidden because of low score. Click to expand.
2
of 6 vote

``````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);``````

Comment hidden because of low score. Click to expand.
0
How about this? {{{ if(null == root) return true; if((root->right != null && root->right-value < root->value) || (root->left != null && root-left->value > root->value) { return false; } return isBST(root->left) && isBST(root->right);
Comment hidden because of low score. Click to expand.
0

@Varun
you code will not be able to check for below BT:

``````10
5            15
4   11      6``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

@Will : BST may have duplicates..
you just need to choose where to put it. if duplicates are present.

left subtree <= root.value & right subtree > root.value
OR
left subtree < root.value & right subtree <= root.value

Comment hidden because of low score. Click to expand.
2
of 2 vote

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"

Comment hidden because of low score. Click to expand.
1
of 1 vote

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
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
struct node
{
int data;
struct node *next;
}*start;

void Check_Bst(node root)
{
Check_Bst(root->left);
Check_Bst(root->right);
}

{
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);
}

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do inorder traversal. Check if the traversed sequence is sorted or not.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

Comment hidden because of low score. Click to expand.
0
of 2 vote

inorder traveling require O(n) space, here is O(1) space with same time complexity algorithm
start recursion from root node, in recursion visit all nodes,
during back tracing start verifying from leaf node.
if at all places we get yes, then it is BST, other wise not.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.) Do inorder traversal of the tree
2.)check whethr the obtained list is in Ascending or Descending Order as per requirement

;)

Comment hidden because of low score. Click to expand.
0

int last_element=-INFINITE;
bool inorder(TreeNode *root)
{
if(root==NULL)
return TRUE;
if(!inorder(root->left)) return false;
if(root->value<last_element)
return false;
last_element = root->value;
if(!inorder(root->right)) return false;
return true;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

return false;
} else {
return checkBST(root.left) && checkBST(root.right);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{That being a BST, the value in the node should obey the rules.
boolean checkBST(Node n, int min, int max){
if(n == null) return true;
if(n.data > max || n.data < min) return false;
return checkBST(n.left, min, n.data) && checkBST(n.right, n.data, max);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int is_bst(node *root)
{
int i,j,k=0,l=0;
if(root == NULL )
{
return 1;
}
if(root->left==NULL||root->left->value<root->value)
k=1;
if(root->right==NULL||root->right->value>root->value)
l=1;
i=is_bst(root->left);
j=is_bst(root->right);
if(i&&j&&k&&l)
return 1;
else
return 0;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````boolean isBST(TreeNode node) {
if (node == null) return true;
isBST(node.left);
isBST(node.right);
return (node.left==null?true:node.data > node.left.data)
&&
(node.right==null?true:node.data < node.right.data);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public boolean isBST(Node n) {
if(n == null) {
return true;
}

bool left = n.left == null || (n.left.value < n.value && isBST(n.left));
bool right = n.right == null || (n.right.value >= n.value && isBST(n.right));

return left && right;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm not very sure, wasn't there a condition like, for a BST to be balanced, the height difference between levels should be 2 at most?

Comment hidden because of low score. Click to expand.
0
of 0 vote

private bool Validate (Tree t)
{
if (t == null)
return true;
if (t.Left != null && t.Value < t.Left.Value)
return false;
if (t.Right != null && t.Value > t.Right.Value)
return false;
return Validate(t.Left) && Validate(t.Right);
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.