Issue checking if binary tree is also binary search tree

Question

I'm trying to solve this problem but I'm having some troubles:

In a binary search tree (BST):

• The data value of every node in a node's left subtree is less than the data value of that node.
• The data value of every node in a node's right subtree is greater than the data value of that node.

Given the root node:

class Node {
    int data;
    Node left;
    Node right;
}

Determine if the binary tree is also a binary search tree

I have this code:

boolean check(Node root) {   

    //node doesn't have any children
    if (root.left == null && root.right == null) {
        return true;
    }

    boolean leftIsBst = true;
    boolean rightIsBst = true;

    if (root.left != null) {
        leftIsBst = (root.left.data < root.data) && check(root.left);
    }

    if (root.right != null) {
        rightIsBst = (root.right.data > root.data) && check(root.right);
    }

    return leftIsBst && rightIsBst;
}

This is working in some cases, but it fails in cases like this one:

As you see, node (4) is in the node (3)'s left subtree, although 4 is greater than 3, so the method should return false. My code returns true, though.

How could I control that case? How can I check that all the values in the left/right subtree are lower/greater than the root (not only the direct child)?

Answer 1

Your definitions are correct (although you don't necessarily need to insist that all the keys are distinct), but your code doesn't implement all the conditions in your definitions. Specifically, you don't enforce the minimum and maximum values in each subtree.

Here is an efficient recursive solution that implements your definitions:

boolean check(Node root) {
    return check(root, INT_MIN, INT_MAX);
}
boolean check(Node n, int minval, int maxval) {
    if (n == null) {
        return true;
    }
    return (
        n.data >= minval && n.data <= maxval &&
        check(n.left, minval, n.data-1) &&
        check(n.right, n.data+1, maxval)
    );
}

Note that I didn't bother checking for overflow in n.data-1 and n.data+1, which you would have to do in real life. If you want to allow duplicate keys, just change these to n.data and you don't have to worry about it.

Answer 2

Something like the following should work

boolean check(Node root) {   

    if (root == null) {
        return true;
    }


    if (root.left != null && max(root.left) > root.data  ) {
        return false
    }

    if (root.right != null && max(root.right) < root.data ) {
        return false;
    }

    return check(root.left) && check(root.right);
}

Note:

• this is fairly inefficient
• you need to implement max()