Checking if the binary tree is also a binary search tree

Question

I am trying to solve this problem, but I am having problems:

In the binary search tree (BST):

• The data value for each node in the left subtree of the node is less than the data value of this node.
• The data value for each node in the right subtree of the node is greater than the data value of this node.

Given the root of the node:

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

Determine if a 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;
}

In some cases, this works, but in such cases, it does not:

As you can see, node (4) is in the left subtree of node (3) , although 4 is greater than 3, so the method should return false. My code is returning true.

? , / /, ( )?

Answer 1

( , ), . , .

, :

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)
    );
}

, n.data-1 n.data+1, . , n.data, .

Answer 2

-

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);
}

:

• max()

Answer 3

Recursive logic is incorrect. I give here the cpp logic. You may need to translate it to Java code.

bool check (Node * root) {

static Node *prev = NULL;

if(root) {

    If(!check(root->left)) return false;

    If(prev != Null && prev->data > root->data) return false;

    Prev = root;

    return check(root->right);


}

return true;

}