Check if Binary Tree is a Binary Search Tree

Question

I tried to write a code to check if a given binary tree is a BST or not. But my code does not pass all the test cases. It passes 6 out of 8 test cases. Why is it wrong/incomplete?

below is my code

public static boolean isBST(BinaryTreeNode<Integer> root) {
    if (root == null) {
        return true;
    }

    boolean left = isBST(root.left);
    boolean right = isBST(root.right);

    boolean currentL = true, currentR = true;

    if (root.left != null) {
        currentL = root.left.data < root.data;
    }

    if (root.right != null) {
        currentR = root.right.data > root.data;
    }

    return left && right && currentL && currentR;
}

using recursion, I get boolean for left and right. Then I return the final value as the answer if all left, right and current subtree is BST. Where is my code lacking? Is it because even if a subtree is BST, its left node might be bigger than some element of main tree that the subtree is part of?

Answer 1

What does your solution say about the following tree?

      --6--
     /     \
   -4-     -8-
  /   \   /   \
 2     7 5     9

The left and right nodes are both valid binary search trees, and 4 is less than 6 and 8 is greater than 6. But doing a BST traversal of this will never find 7 or 5.

You need to ensure that the max value in the left node is less than the root, and vice versa for the right node.