Infosys Interview Question for Software Engineer / Developers

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

bool is_BST(Tree* x, int* min, int* max)
{
int lmin, lmax;
int rmin, rmax;
Tree *l, *r;

if (x == NULL) {
*min = +inf;
*max = -inf;
return true;
}

l = x->left;
r = x->right;

if (!(bl = is_BST(l,&lmin,&lmax)))
return false;

if (!(br = is_BST(r,&rmin,&rmax)))
return false;

// compute the min & max
*min = min {x->key,lmin,rmin};
*max = max {x->key,lmax,rmax};

return (x->key >= lmax && x->key <= rmin);
}

int main(...) {
Tree* x;
int min, max;
...
return is_BST(x,&min,&max);
}

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

in order to check if a tree is BST, one must do an in-order traversal and check if the elements are in increasing order.

suppose the tree nodes contain int as values.

bool isBST(node *root) {
if (!root) return true; //if no tree, it is BST, or false depending on your def.

vector<int> v;

traverseInorder(root, v);

int i=0;
while (i+1 < v.size()) {
if ((int)v.get(i+1) > (int)v.get(i)) return false;
}

return true;
}

//recursive
void traverseInorder(node *root, vector<int> &v) {
if (!root) return;
else {
traverseInorder(root->left);
v.insert(root->value);
traverseInorder(root->right);
}
}

//or iterative
void traverseInorder(node *root, vector<int> &v) {
if (!root) return;

stack<node *> s;
s.push(root);

while(!s.empty()) {
node *cur = s.pop();

if (cur->left) s.push(cur->left);
v.insert(cur->value);
if (cur->right) s.push(cur->right);
}
}

I think the above solution will work as well, but this solution is cleaner and it gives the option to stay away from recursion. At an interview, I would suggest this one first and then if the interviewer wants something else, i would give the solution above.

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

is the iterative one correct? Seems not inorder transversal.

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

dude I don't think above non iterative solution is correct.

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

int min=INT_MIN;
int max=INT_MAX;

bool checkBST(tree* root,int min,int max)
{
if(root==NULL)return true;

if(root->data<min || root->data>max)return false;

return (checkBST(root->left,min,root->data) && checkBST(root->right,root->data,max) );

}

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

inorder traversal. keep two variables. while processing the node check if it is greater than the previous one. Break if it disagrees at any point

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.