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