Validate a binary search tree

Pass an allowed (low, high) range down the tree. Every key must fit its range, not just beat its parent.

The idea

A BST needs every key in a left subtree to be smaller than the node, and every key in a right subtree to be larger, all the way down, not just for direct children. So carry a range (low, high) into each call. Going left, the node becomes the new upper bound; going right, it becomes the new lower bound. A key outside its range breaks the tree, even when it looks fine next to its parent.

Code

public bool IsValidBST(TreeNode root) =>
    Valid(root, long.MinValue, long.MaxValue);

private bool Valid(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return Valid(node.left, low, node.val)
        && Valid(node.right, node.val, high);
}

Tips

• The default tree passes every parent-child test (55 > 40), yet 55 sits in 50's left subtree, so it must be less than 50. Only the range catches that.
• Use long bounds (or nullable ints) so a node holding int.MinValue or int.MaxValue is not wrongly rejected.
• An inorder traversal that checks each key is strictly larger than the previous one is an equally good O(n) answer.

In the .NET library

TreeNode is your own class in C#; there is no built-in binary tree type to validate. SortedSet<T> keeps its own red-black tree valid internally, so this check is only needed for trees you build yourself.