Validate BST

My usual mistake for this problem:
You can not just compare node.left.value < node.value < node.right.value.
This does not handle edge cases such as:

20 is > 5 but it should be lower than 10! You have to make sure the left one is lower than all the nodes above.

Solution

Time Complexity: O(N) where N is the count of nodes. Can’t do better.
Space Complexity: O(log N) due to recursion on a balanced tree.

Why space complexity of O(log N)?

ONLY IF BALANCED!

But aren’t you adding one entry to the recursive stack for each node? isn’t that O(n) regardless of how the BST is constructed?. The stack is cleaned up when the recursive function reaches a leaf node (when you start to pop and go up). So if the tree is balanced, the stack will never be deeper than log n.

See here for more info http://stackoverflow.com/a/21546734/1132522

boolean checkBST(Node root, int minValue, int maxValue) {
    if (root == null) {
        return true;
    }

    if (root.data < minValue || root.data > maxValue) {
        return false;
    }

    return ( checkBST(root.left, minValue, root.data - 1)
            &&  checkBST(root.right, root.data + 1, maxValue)
         );
}

boolean checkBST(Node root) {
    return checkBST(root, 0, 10000);
}