Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question
    
Is it a pseudocode? –  palacsint Jan 25 '13 at 7:48
add comment

closed as off topic by palacsint, Jerry Coffin, Jeff Vanzella, James Khoury, almaz Jan 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.

3 Answers

up vote 1 down vote accepted

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);
}
share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Could you please take a look at my edit? –  John Roberts Jan 24 '13 at 14:26
add comment

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.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.