Amazon Flipkart Groupon Interview Question
Software Engineer / DevelopersCountry: -
Interview Type: In-Person
int arr[10];
//7 element
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
check(root)
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 element
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
What if the number of nodes are in billions, then doing inorder traversal is the worst method for this program #ask in amazon.
@Raj : If number of nodes is in billions, then checking this will take a lot of time whichever way you use, don't you think?
The inorder travesal will be a good way to use if the discrepancy is near the bottom of the tree; as it will return false as soon as it finds two nodes that are not in correct order. In the same case(discrepancy near the bottom of the tree), if you use the top-down recursive approach, it will be slower IMO. I think the efficiency an approach depends on where exactly the fault is - somewhere near the root of the tree, or near the deepest leaves..
It's a mix of c and pseudo code. The only problem is if the first element(root) is equal to MIN_INT. An extra if statement can overcome that condition but I think this should work otherwise.
1 int checkbst(struct node *root, int min, int max)
2 {
3 if(root == NULL)
4 return 1;
5
6 return ( (root->data >min && root->data <= max) && checkbst(root->le ft,min, root->data) && checkbst(root->right,root->data,max) );
7
8 }
9
10 int main()
11 {
12 if(checkbst(root, MIN_INT, MAX_INT))
13 print "YES";
14 }
Java code: call checkBST (root, Integer.MIN_Value, Integer, MAX_Value)
Boolean checkBST (node root, int min, int max) {
if(root == null)
return true;
if(min < root.data && root.data < max)
return checkBST(root.left, min, root.data) && checkBST(root.right, root.data, max);
else
return false;
}
I am thinking inorder traversal too.
1. Note the root element.
2. Do inorder traversal of the tree and store in an array.
3. Find the root element in the array.
4. verify if its really sorted.
My question here would be what if the same question was to verify if it was a min or max heap. Then do a preorder traversal?
ur solution though completely valid will still require O(n) space for the array and will have to go through each an every node, although it will still be O(n) time complexity..
how about doing a simple breadth first traversal and before queueing the nodes just checking for the condition:
if (root->left != 0)
{
if (root->data < root->left->data)
{
printf("Not a BST");
break;
}
queue.enqueue(root->left);
}
if (root->right != 0)
{
if (root->data > root->right->data)
{
printf("Not a BST");
break;
}
queue.enqueue(root->right);
}
I think this will work too and will save the extra O(n) space. Also u can abort as soon as u find if its not a BST.
Let me know if something is wrong
I assume you put your code in some while loop. I think you are just comparing left node value and right node value with the root (albeit correctly), but your code doesn't handle all the past parent values in which case you get some errors
like when the tree is
6
/ \
2 8
/ \
1 4
/ \
3 7
This is not a BST but with your code it will say it is, because all it does when the control is at 4 checks if 3 is smaller than 4 and 7 is greater than 4
Let me know if i am missing some thing obvious?
I guess the recursive code is as follows:
find (node *root)
{
if (root != NULL) // if the node is null return true
{
bool leftNode = find (root->left);
bool rightNode = find (root->right);
if (leftNode && rightNode) //both the criteria should agree else return false
{
if (root->right == NULL && root->left == NULL) //leaf node
return true;
else if (root->right == NULL) //When the right child is null
{
if (root->data > root->left->data)
return true;
else
return false;
}
else if (root->left == NULL) //when left child is null
{
if (root->info < root->right->info)
return true;
else
return false;
}
else
{
if (root->info > root->left->info && root->info < root->right->info)
return true;
else
return false;
}
}
return false;
}
return true;
}
I think this way should be simple and clear, is there anything wrong? Hope to get your critiques.
public static boolean findIsBFS(Node root)
{
if(root==NULL || (!root.leftchild && !root.rightchild))
{
return true;
}
if(root.leftchild.value>root.value || root.rightchild.value<root.value )
{
return false;
}
return findIsBFS(root.leftchild) && findIsBFS(root.rightchild);
}
<pre lang="" line="1" title="CodeMonkey95493" class="run-this">typedef struct tnode {
int i;
struct tnode* lt;
struct tnode* rt;
} TreeNode;
bool IsValidBST(TreeNode *node, int min, int max)
{
if ((node == NULL) || ((node->lt == NULL) && (node->rt == NULL)))
{
return true;
}
if ((node->i < max) &&
(node->i > min) &&
IsValidBST(node->lt, min , node->i) &&
IsValidBST(node->rt, node->i , max ))
{
return true;
}
}</pre><pre title="CodeMonkey95493" input="yes">The code is very straightforward. as you go down the tree, keep a track of the max and min values that a particular node can take.
you can call this method with MININT and MAXINT values for min and max.
Let me know your comments</pre>
We should leverage properties of binary search tree: the left child value is less or equal to the node value and the right child value should be greater or equal than the node value. And check that property for each node. The code is using preorder traversal.
Assuming that null child is ok.
Let's assume that all left children are fine, but the root node is not, with large number of children on the left (balanced or non-balanced tree, does not matter), with "in order" traversal the code will have to reach for the last node on the left and only then go up until finding out that the root itself does not comply. It should be fail-fast, fail-early algorithm, which is "pre-order" here. If we were counting non-complied nodes, then the order is irrelevant. Agreed?
What if the tree is right heavy at the root? And there is a discrepancy wrt to BST near right tree's leaves?
I think inorder traversal will serve fine in general average case.
Also, we can have a mix of both the above approaches.
If node is less than left child or greater than right child, terminate with false.
Else compute inorder. :P
What you just described as "mix of both" is called "pre-order", exactly the algorithm in the code above.
Pre-order: root -> left child -> right child
In-order: left child -> root -> right child
Post-order: left child -> right child -> root
1.find the max and min of the given tree, in BST its the right most and left most elements,so thorugh findmax() and findmin() we get the same
2.we increment the minnode and decrement maxnode ,so that the checking we are doing won't fail at the leftmost and rightmost nodes
3.traverse through each node and check wheteher they lie in the suiatable range or not
4.revert back the change we made
typedef struct node
{
int data;
struct node *right;
struct node *left;
}node;
node* findmax(node *root);
node* findmin(node *root);
int check_BST(node *root, int min, int max);
int main()
{
int min,max;
node *root,*maxnode,*minnode;
maxnode= findmax(root);
minnode= findmin(root);
if(maxnode == NULL || minnode ==NULL)
return -1;
min=min->data++;
max-max->node--;
if(check_BST(root,min,max));
printf("\n valid BST");
else
printf("\n non-valid BST");
min->data++;
max->data--;
}
node* findmin(node *root)
{
if(root== NULL)
return NULL;
node *temp1 = malloc(sizeof(node));
if(!temp1)
printf("\n memmory not available");
while(root->left)
root=root->left;
temp1=root;
return temp1;
}
node* findmax(node *root)
{
if(root== NULL)
return NULL;
node *temp2 = malloc(sizeof(node));
if(!temp2)
printf("\n memmory not available");
while(root->right)
root=root->right;
temp2=root;
return temp2;
}
int check_BST( node *root, int min, int max)
{
if(root == NULL)
return 1;
if(root->data < max && root->data >min)
{
return( check_bst(root->left,min,root->data) && check_BST(root->right,root->data, max));
}
else
return 0;
}
1.find the max and min of the given tree, in BST its the right most and left most elements,so thorugh findmax() and findmin() we get the same
2.we increment the minnode and decrement maxnode ,so that the checking we are doing won't fail at the leftmost and rightmost nodes
3.traverse through each node and check wheteher they lie in the suiatable range or not
4.revert back the change we made
typedef struct node
{
int data;
struct node *right;
struct node *left;
}node;
void findmax(node *root,node **maxnode);
void findmin(node *root, node **minnode);
int check_BST(node *root, int min, int max);
int main()
{
int min,max;
node *root,**maxnode,**minnode;
findmax(root);
findmin(root);
if(*maxnode == NULL || *minnode ==NULL)
return -1;
min=(*min)->data++;
max=(*max)->node--;
if(check_BST(root,min,max));
printf("\n valid BST");
else
printf("\n non-valid BST");
(*min)->data++;
(*max)->data--;
}
void findmin(node *root, node **minnode)
{
if(root== NULL)
return NULL;
while(root->left)
root=root->left;
*minnode=root;
}
void findmax(node *root,node **maxnode)
{
if(root== NULL)
return NULL;
while(root->right)
root=root->right;
*maxnode=root;
}
int check_BST( node *root, int min, int max)
{
if(root == NULL)
return 1;
if(root->data < max && root->data >min)
{
return( check_bst(root->left,min,root->data) && check_BST(root->right,root->data, max));
}
else
return 0;
}
here is simpler code to understand.
bool isThisABST(struct node* mynode)
{
if (mynode==NULL) return(true);
if (node->left!=NULL && mynode->left->info > mynode->data)
return(false);
if (node->right!=NULL && mynode->right->info <= mynode->data)
return(false);
if (!isThisABST(node->left) || !isThisABST(node->right))
return(false);
return(true);
}
I think this works. Have to check if the max of the left subtree is less than current node and min of the right subtree is always greater.
struct MinMax {
int min;
int max;
};
struct MinMax *IsBST(Node *root)
{
struct MinMax *newminmax;
if (!root) return root;
if (!root -> left && !root -> right) {
newminmax = malloc(sizeof(struct MinMax));
newminmax -> min = newminmax -> max = root -> value;
return newminmax;
}
struct MinMax *left, * right;
left = IsBST(root -> left);
right = IsBST(root -> right);
if (root -> left) {
if (!left || left -> max > root -> data)
return NULL;
newminmax = left;
}
if (root -> right) {
if (!right || right -> min < root -> data)
return NULL;
if (!newminmax)
newminmax = right;
newminmax -> max = right -> max;
}
return newminmax;
}
My recursive solution is as follow :
Bool IsBst ( Tree root )
{
if ( root == NULL )
return true;
if ( ( root->left == NULL && root->right == NULL ) || /* case 1 */
( root->left == NULL && root->data < root->right->data ) || /* case 2 */
( root->right == NULL && root->data > root->left->data ) || /* case 3 */
( root->right != NULL && root->left != NULL && root->data > root->left->data && root->data < root->right->data) ) /* case 4 */
{
return IsBst( root->left ) && IsBst( root->right ) ; /* current node is OK, check children recursively */
}
else
return false ; /* current node is Bad, return false directly */
}
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
//7 element
int arr[10];
void check(tree*root) //inorder traverse
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
check(root);
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
Approach
The solution is to check, for every node in the tree, the min and max key values of the nodes in its left sub tree is less than the value of its key and the min and max key values in its right sub tree is greater than the value of its key. This can be achieved by recursion.
The idea is to “bubble up” the min and max values of a node’s sub tree, after satisfying the conditions above, to its parent node, which will in turn repeat the same process. The algorithm is designed around pre-order tree traversal and solves the problem in O(n) (linear) time.
Algorithm
For the current node:
Step1: Get the min and max values for left sub tree if left child exists
Step2: If the min and max values are greater or equal to current node’s key, return “Not BST”
Step 3: If there is no left child, set the min value to current node’s key value
Step 4: Get the min and max values for right sub tree if right child exists
Step 5: If the min and max values are lesser or equal to current node’s key, return “Not BST”
Step 6: If there is no right sub tree, set the min value from step 1 and the max value to current node’s key value
Step 7: Return the min value from step 1 and max value from step 6
You can find the code and the explanation using a pictorial representation of the binary tree in my blog linearspacetime[dot]blogspot[dot]com
public static boolean isBST(BinaryTree<Integer> binaryTree, Integer lowerBoundExclusive, Integer upperBoundExclusive){
System.out.println("binaryTree: " + binaryTree.getInfo());
BinaryTree<Integer> binaryTreeLeft = binaryTree.getLeftChild();
if(binaryTreeLeft != null && (binaryTree.getInfo().compareTo(binaryTreeLeft.getInfo()) < 1 || (lowerBoundExclusive != null && lowerBoundExclusive.compareTo(binaryTreeLeft.getInfo()) > -1)))
return false;
BinaryTree<Integer> binaryTreeRight = binaryTree.getRightChild();
if(binaryTreeRight != null && (binaryTree.getInfo().compareTo(binaryTreeRight.getInfo()) > -1 || (upperBoundExclusive != null && upperBoundExclusive.compareTo(binaryTreeRight.getInfo()) < 1)))
return false;
boolean isLeftSubTreeBST = binaryTreeLeft == null ? true : isBST(binaryTreeLeft, lowerBoundExclusive, binaryTree.getInfo());
if(!isLeftSubTreeBST)
return false;
boolean isRightSubTreeBST = binaryTreeRight == null ? true : isBST(binaryTreeRight, binaryTree.getInfo(), upperBoundExclusive);
if(!isRightSubTreeBST)
return false;
return true;
}
bool isBST(Node* root, int& previousValue)
{
if ( root )
{
if ( !isBST(root->m_left,previousValue) )
{
return false;
}
std::cout<<"\t"<<root->m_data<<" prev :"<<previousValue;
if ( root->m_data < previousValue )
{
return false;
}
previousValue = root->m_data;
if ( !isBST(root->m_right, previousValue) )
{
return false;
}
}
return true;
}
This should work, even if MAX_INT or MIN_INT are in the tree -
typedef struct Node {
struct Node *l, *r;
int v;
} Node;
// Parse tree from stdin
void parse_tree(Node **);
// Check if tree is BST, and if so get min and max values of tree
int is_bst(Node * node, int *min, int *max)
{
int lmax, rmin;
if (node == NULL)
return 1;
else
*max = *min = node->v;
return (node->l == NULL ||
(is_bst(node->l, min, &lmax) && (lmax < node->v))
) &&
(node->r == NULL ||
(is_bst(node->r, &rmin, max) && (node->v < rmin))
);
}
int main()
{
Node *head = NULL;
parse_tree(&head);
int max, min;
is_bst(head, &max, &min) ? printf("BST\n") : printf("BAD\n");
}
private static boolean IsBST(BST tree, int rootValue) {
if (tree == null) {
return true;
}
if ((tree.leftNode != null && tree.leftNode.value > rootValue)
&& (tree.rightNode != null && tree.rightNode.value < rootValue)) {
return false;
}
return IsBST(tree.leftNode, rootValue) && IsBST(tree.rightNode, rootValue);
}
<pre lang="" line="1" title="CodeMonkey73917" class="run-this">/**
* Created by IntelliJ IDEA.
* User: andrey
* Date: 10/10/11
* Time: 10:50 AM
*/
public class BinarySearchTreeOrNot {
public static void main(String[] args) {
BinarySearchTreeOrNot test = new BinarySearchTreeOrNot();
test.run();
}
void run() {
// test with binary search tree
Node bst = createBinarySearchTree();
boolean result = isBinarySearchTreeNode(bst);
System.out.println(result);
// test with binary tree
Node bt = createBinaryTree();
result = isBinarySearchTreeNode(bt);
System.out.println(result);
}
boolean isBinarySearchTreeNode(Node node){
if (node == null) return true;
if (node.left != null && node.left.value > node.value) return false;
if (node.right != null && node.right.value < node.value) return false;
return isBinarySearchTreeNode(node.left) && isBinarySearchTreeNode(node.right);
}
Node createBinarySearchTree(){
Node one = new Node(1);
Node four = new Node(4);
Node three = new Node(3);
three.left = one;
three.right = four;
Node five = new Node(5);
Node six = new Node(6);
Node seven = new Node(7);
Node nine = new Node(9);
five.left = three;
five.right = seven;
seven.left = six;
seven.right = nine;
return five;
}
Node createBinaryTree(){
Node five = new Node(5);
Node eight = new Node(8);
Node one = new Node(1);
Node sixteen = new Node(16);
Node three = new Node(3);
Node nine = new Node(9);
Node two = new Node(2);
five.left = eight;
five.right = three;
eight.left = one;
eight.right = sixteen;
three.left = nine;
three.right = two;
return five;
}
class Node {
int value;
Node right;
Node left;
Node(int value){
this.value = value;
}
}
}
</pre><pre title="CodeMonkey73917" input="yes">
</pre>
replace
isBinarySearchTreeNode(node.left) && isBinarySearchTreeNode(node.right);
with
isBinarySearchTreeNode(node.left) || isBinarySearchTreeNode(node.right);
Care to explain?
|| will check the left part of the condition and if it's true, then return back true, even if the right child is not BST.
&& is correct
Won't work. In the following case. It is a binary tree, but not a valid BST.
10
/ \
5 12
\
7
/ \
3 9
Nice test case, Ram!!! You absolutely right! One of the solutions would be to pass the limits, updating them along the way. I rewrote the code and it works for the test case above. I'm glad you posted your comment.
boolean isBinarySearchTreeNode(Node node, int left, int right){
if (node == null) return true;
if (node.value < left || node.value > right) return false;
if (node.left != null && node.left.value > node.value) return false;
if (node.right != null && node.right.value < node.value) return false;
return isBinarySearchTreeNode(node.left, left, node.value) && isBinarySearchTreeNode(node.right, node.value, right);
}
The same algorithm was posted by pseudo_coder below.
int arr[10];
void check(tree*root)
{
if(root->left!=NULL)
check(root->left);
arr[i++]=root->val;
if(root->right!=NULL)
check(root->right);
}
int main::
int found=0;
for(int i=0;i<=7; i++)
{
cout<<"\n "<<arr[i];
if((arr[i]>arr[i+1])&&i!=7 )//7 elements
found=1;
}
if (found==0)
cout<<"\nBINARY SEARCH TREE IT IS:SORTED";
else
cout<<"NOT A BINARY SEARCH TREE";
return 0;
boolean isBST(node root) {
if ( root == null || (root.left == null && root.right == null )) {
return true;
}
if ( root.left == null && root.right == null ) {
return true;
}
if ( root.left > root.right ) {
return false;
}
return (isBST(root.left) && isBST(root.right));
}
@sjain
I haven't voted your comment down, though, after seeing your algorithm I too realized the problem(as probably the other lady/gentleman, who voted down your comment would too have) that the following condition alone is not sufficient.
if ( root.left > root.right ) {
return false;
}
You are checking for correctness only at parent-child level, whereas you would need to check for correctness at subtree level.
For ex: Suppose you are at a node in the right subtree of the whole tree and your above condition is satisfied. But, how will you ensure that your
root.left
is greater than all of the elements in the left sub-tree of the whole tree?
The recursive method which takes min and max permissible values as parameters and which checks at each sub-tree level that the node value is lying within those parameters works correctly. You may want to check solutions at: question?id=11146157
Do an Inorder traversal of the tree and check if that is sorted. If in-order traversal is sorted then it is a BST
- vinaysachdeva23 October 13, 2011