How to check if a binary tree is a binary search tree

A Binary Search Tree (BST) is a binary tree where each node has a key and meet the following requirements:

• The left subtree of a node contains nodes with keys smaller then the node's key
• The right subtree of a node contains nodes with keys larger then the node's key
• The left and right subtrees are binary search trees

 

 

Here is how a node could look like.

   public class TreeNode
   {
       public int Value;
       public TreeNode Left;
       public TreeNode Right;

       public TreeNode(int value)
       {
           Value = value;
       }
   }

Algorithm

If a binary tree meets the definition of a binary search tree. It's mean a binary tree is a binary search tree. For simplicity let's assume Node contains an int value. With this assumption, we can expect all values will be between long.MinValue and long.MaxValue. And what is left, is just go thru a binary tree and check is a node value between min and max values.

    public bool IsValid(TreeNode root)
    {
        return IsValid(root, long.MinValue, long.MaxValue);
    }

    private static bool IsValid(TreeNode node, long min, long max)
    {
        if (node == null)
        {
            return true;
        }

        if (node.Value >= max || node.Value <= min)
        {
            return false;
        }

        return IsValid(node.Left, min, node.Value) && IsValid(node.Right, node.Value, max);
    }