[ALGO] Is Binary Search Tree

Given a binary tree, verify if it is Binary Search Tree


Madhur Kumar Tanwani said...

Two solutions :
1.> (mine) post order traversal, get max from left tree and min from right tree. Ensure curr > (max from left) and curr < (min from right). do this for all nodes in recursion

2.> (colleague) inorder traversal - the traversal should not break sorted order if this is a BST.

Madan Kumar said...

bool isBST(struct node *root) {
if (root == NULL) return true;
if (root->left && maxVal(root->left) > root->data) return false;
if (root->right && minVal(root->right) < root->dasta) return false;
return true;

Madhur Kumar Tanwani said...

Though the solution is perfect, the running time would not be so good.

I suppose those could be improved as well with extra logic though.

The advantage i see of the post-order approach over this one is that the min & max values can be thrown up to the root node, where the check is to be made - so memory usage is O(1) and running time is not affected

Akhil said...

I think the best way would be to do inorder traversal of the tree and when the element visited has a value less than the previous one, declare it as not a BST.
Time - O(n)
Space - O(1)