Validate Binary Search Tree.md

Provided code

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

Solution

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean isValidBST(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        } else if (node.val <= min || node.val >= max) {
            return false;
        }
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }
}

Time/Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(log n) if balanced tree. O(n) if not balanced.

Links

• github.com/RodneyShag