Leetcode: Given a binary tree, determine if it is a valid binary search tree (BST).

https://leetcode.com/problems/validate-binary-search-tree/

BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Valid BST

    2
   / \
  1   3

    5
   / \
  3   10
 / \
1   4

Invalid BST

    3
   / \
  1   2

    6
   / \
  3   10
 / \
1   7

At first pass, it may seem reasonable to have a check where if the condition left.val < root.val < right.val satisfies then a node is valid and same check can be done for each node. But this condition failes in certain cases, especially in 2nd example of Invalid BST. The trick to solve the problem is one need to maintain MIN & MAX counter from the root and as tree is traversed update the counter.

• When traversing left, the root.val should be set to MAX
• When traversing to right, MIN value should be set to MIN

class TreeNode {
    int val;
    TreeNode left;
 	TreeNode right;
	TreeNode(int x) { val = x; }
 }

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

private boolean isValidBST(TreeNode root, long minValue,long maxValue) {
	if (root == null)
		return true;
	if (root.val <= minValue || root.val >= maxValue)
		return false;
	return isValidBST(root.left, minValue, root.val) && 
		isValidBST(root.right, root.val, maxValue);
 }
}