It’s a pretty well-known problem with the following answer:
public boolean isValid(Node root) {
return isValidBST(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
private boolean isValidBST(Node node, int l, int h) {
if(node == null)
return true;
return node.value > l
&& node.value < h
&& isValidBST(node.left, l, node.value)
&& isValidBST(node.right, node.value, h);
}
The recursive call makes sure that subtree nodes are within the range of its ancestors, which is important. The running time complexity will be O(n) since every node is examined once.
The other solution would be to do an inorder traversal and check if the sequence is sorted, especially since you already know that a binary tree is provided as an input.