public int Value { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
public Node(int value, Node left, Node right)
public class BinarySearchTree
public static bool IsValidBST(Node root)
if (root == null) return true;
int? leftMin,leftMax,rightMin,rightMax;
return IsValidBSTInternal(root.Left, out leftMin, out leftMax)
&& IsValidBSTInternal(root.Right, out rightMin, out rightMax)
&& (!leftMax.HasValue || root.Value >= leftMax.Value)
&& (!rightMin.HasValue || root.Value < rightMin);
private static bool IsValidBSTInternal(Node root, out int? min, out int? max)
if (IsValidBSTInternal(root.Left, out leftMin, out leftMax)
&& IsValidBSTInternal(root.Right, out rightMin, out rightMax)
&& (!leftMax.HasValue || root.Value >= leftMax.Value)
&& (!rightMin.HasValue || root.Value < rightMin.Value))
min = leftMin.HasValue ? leftMin : root.Value;
max = rightMax.HasValue ? rightMax : root.Value;
min = leftMin.HasValue ? leftMin : root.Value;
max = rightMax.HasValue ? rightMax : root.Value;
public static void Main(string[] args)
Node n1 = new Node(1, null, null);
Node n3 = new Node(3, null, null);
Node n2 = new Node(2, n1, n3);
Console.WriteLine(IsValidBST(n2));