Algorithm to determine if binary tree is a Binary Search Tree (BST) Continuing with algorithms I've implemented a binary search tree validator. I don't like the two boolean variables within NodeFollowsBSTContract as it feels too complicated. I feel like it should be cleaned up but don't see how, yet.
Also, before each recursive step down, to check child nodes, a new list is created. Is there's a better way to implement this check that doesn't repeatedly create new lists?
public class BinaryTreeNode
{
    public BinaryTreeNode Left { get; set; }
    public BinaryTreeNode Right { get; set; }

    public int? Value { get; }

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

public class ValidateBST
{
    BinaryTreeNode _root;
    public ValidateBST(BinaryTreeNode root)
    {
        _root = root;
    }

    public bool IsBinarySearchTree()
    {
        if ((_root.Left?.Value ?? 0) &lt;= (_root.Value)
            || (_root.Right?.Value ?? 0) &gt; (_root.Value))
        {
            var listIncludingRootValue = new List&lt;int&gt;()
            {
                _root.Value.Value
            };

            var leftLegValid = NodeFollowsBSTContract(_root.Left, new List&lt;int&gt;(), new List&lt;int&gt;(listIncludingRootValue));

            var rightLegvalid = NodeFollowsBSTContract(_root.Right, new List&lt;int&gt;(listIncludingRootValue), new List&lt;int&gt;());

            return leftLegValid &amp;&amp; rightLegvalid;
        }
        else
        {
            return false;
        }   
    }

    private bool NodeFollowsBSTContract(BinaryTreeNode node, List&lt;int&gt; parentSmallerValues, List&lt;int&gt; parentLargerValues)
    {
        if (node == null)
        {
            return true;
        }

        bool isLessThanAllParentLargerValues = !parentLargerValues.Any()
            || parentLargerValues.Where(value =&gt; node.Value.Value &lt;= value).Count() == parentLargerValues.Count;

        bool isGreaterThanAllParentSmallerValues = !parentSmallerValues.Any()
            || parentSmallerValues.Where(value =&gt; node.Value.Value &gt; value).Count() == parentSmallerValues.Count;

        if (!isLessThanAllParentLargerValues || !isGreaterThanAllParentSmallerValues)
        {
            return false;
        }

        if (node.Left != null)
        {
            var updatedLargerValues = GenerateUpdatedLists(node.Value.Value, parentLargerValues);
            var updatedSmallervalues = new List&lt;int&gt;(parentSmallerValues);

            if (!NodeFollowsBSTContract(node.Left, updatedSmallervalues, updatedLargerValues))
            {
                return false;
            }
        }

        if (node.Right != null)
        {
            var updatedvalues = GenerateUpdatedLists(node.Value.Value, parentSmallerValues);

            if (!NodeFollowsBSTContract(node.Right, updatedvalues, parentLargerValues))
            {
                return false;
            }
        }

        return true;
    }

    private List&lt;int&gt; GenerateUpdatedLists(int addValue, List&lt;int&gt; values)
    {
        var updatedValues = new List&lt;int&gt;(values)
        {
            addValue
        };

        return updatedValues;
    }
}
You can tremendously reduce the memory requirements of this code by acknowledging that you can replace the lists you use by single values:
private static bool IsBinarySearchTree(Node root, int max, int min)

this allows you to successively tighten the bounds on subtrees without storing the values you traversed in a list:
public static bool IsBinarySearchTree() 
{
    var valid = true;
    // could be simplified to a single expression, but this is easier to understand
    valid &amp;= IsBinarySearchTree(_root.Left, _root.Value, Int.MIN_VALUE);
    valid &amp;= IsBinarySearchTree(_root.Right, Int.MAX_VALUE, _root.Value);
    return valid;

}

This should already be enough to write the recursive method and I think you'll learn more if I don't spoil this for you :)
But if you want a spoiler...

 private static bool IsBinarySearchTree(Node root, int max, int min)
 {
      // if there's no node
      if (root == null)  return true;
      if (root.Value &lt;= min || root.Value &gt;= max)
      {
          return false;
      }
      return IsBinarySearchTree(root.Left, root.Value, min)
        &amp;&amp; IsBinarySearchTree(root.Right, max, root.Value);
 }

This simplification is possible because you only need store the smallest larger element and the largest smaller element to be able to guarantee that relation holds for the node you're currently examining.