Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite
1

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 at 7:48

closed as off topic by palacsint, Jerry Coffin, Jeff Vanzella, James Khoury, almaz Jan 30 at 16:46

Questions on Code Review Stack Exchange are expected to relate to code review request within the scope defined in the FAQ. 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 closed questions here.

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 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 at 4:03
up vote 3 down vote

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 at 14:26
up vote 0 down vote

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

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