# Check Whether Binary Tree is a Binary Search Tree [closed]

Could someone please verify the validity of my algorithm? I am assuming that a non-null value is initially passed into the function:

boolean isBinarySearchTree(Node *root){
if(!root)
return true;
if(root.left.data<root.data && root.right.data>root.data){
isBinarySearchTree(root.left);
isBinarySearchTree(root.right);
}
else
return false;
}


EDIT:

boolean driver(Node *root){
return doesFollowBSTRulesLeft(root, root.value) && doesFollowBSTRulesRight(root, root.value);
driver(root.left);
driver(root.right);
}

boolean doesFollowBSTRulesLeft(Node *root, int originalRootValue){
if(root.value >= originalRootValue)
return false;
doesFollowBSTRulesLeft(root.left, originalRootValue);
doesFollowBSTRulesLeft(root.right, originalRootValue);
return true;
}

boolean doesFollowBSTRulesRight(Node *root, int originalRootValue){
if(root.value <= originalRootValue)
return false;
doesFollowBSTRulesRight(root.left, originalRootValue);
doesFollowBSTRulesRight(root.right, originalRootValue);
return true;
}

-

## closed as off topic by palacsint, Jerry Coffin, Jeff Vanzella, James Khoury, almazJan 30 '13 at 16:46

Questions on Code Review Stack Exchange are expected to relate to code review request within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

Is it a pseudocode? –  palacsint Jan 25 '13 at 7:48

Two changes:

1. remove the two lines of unnecessary (unreachable) code in Driver method
2. add the check of null for doesFollowBSTRulesLeft and doesFollowBSTRulesRight methods

Following is the edited version

 boolean driver(Node *root){
return doesFollowBSTRulesLeft(root, root.value) && doesFollowBSTRulesRight(root, root.value);
}

boolean doesFollowBSTRulesLeft(Node *root, int originalRootValue){
if(root is null || root.value >= originalRootValue)
return false;
Return doesFollowBSTRulesLeft(root.left, originalRootValue) &&
doesFollowBSTRulesLeft(root.right, originalRootValue);
}

boolean doesFollowBSTRulesRight(Node *root, int originalRootValue){
if(root is null || root.value <= originalRootValue)
return false;
Return doesFollowBSTRulesRight(root.left, originalRootValue) &&  doesFollowBSTRulesRight(root.right, originalRootValue);
}

-
What did you change? What was wrong with the original code? –  svick Jan 26 '13 at 14:55
@svick Two changes: 1) remove the two lines of unnecessary(unreachable) code in Driver method, 2) add the check of null for doesFollowBSTRulesLeft and doesFollowBSTRulesRight methods. –  peanut Jan 30 '13 at 4:03

Not quite. Firstly, you'd want to change your algorithm to return isBinarySearchTree(root.left) && isBinarySearchTree(root.right);.

However, this algorithm isn't quite correct, either. For example, say the root is 5, with (2, 8) as left, right children respectively. Then say 8 has left/right children (4, 10). The current algorithm will return true, because 4 < 8 and 10 > 8. However, 4 < 5 and shouldn't be on the right branch of the tree. This isn't accounted for.

To fix this, you'll need to use some way of seeing if the value is somehow part of the left or right tree branch, and add another comparison to check if that value is then less than or greater than the root value.

Hint: You can also do this with an in-order traversal.

-
Could you please take a look at my edit? –  John Roberts Jan 24 '13 at 14:26

Another way of going about it is to do a Breadth-First traversal of the tree and check the resulting list to ensure that all values have strict weak ordering, i.e., are sorted.

-