## Infosys Interview Question

Software Engineer / Developersin 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.

- Billy June 16, 2007