IsBst.cs

using System.Collections.Generic;
using System.Linq;
using Xunit;

namespace IsBST
{
    public class BSTTester
    {
        public static bool IsBST(Node root)
        {
            if (root == null)
            {
                return false;
            }
            if (root.Children == null)
            {
                return true;
            }

            if (root.Children[0].Value >= root.Value || root.Children[1].Value <= root.Value)
            {
                return false;
            }
            else
            {
                return root.Children.All(IsBST);
            }
        }
    }

    public class Tests
    {
        [Fact]
        public void IsBST_BinarySearchTree_True()
        {
            var tree = new Node(100, new List<Node>
            {
                new Node(50, new List<Node>
                {
                    new Node(25),
                    new Node(75)
                }),
                new Node(150, new List<Node>
                {
                    new Node(125),
                    new Node(175)
                })
            });

            var result = BSTTester.IsBST(tree);

            Assert.Equal(result, true);
        }

        [Fact]
        public void IsBST_EmptyTree_False()
        {
            Node tree = null;

            var result = BSTTester.IsBST(tree);

            Assert.Equal(result, false);
        }

        [Fact]
        public void IsBST_NonBinarySearchTree_False()
        {
            Node tree = new Node(100, new List<Node>
            {
                new Node(50, new List<Node>
                {
                    new Node(80), // Not a binary search tree.. should be less than value.
                    new Node(75)
                }),
                new Node(150, new List<Node>
                {
                    new Node(125),
                    new Node(175)
                })
            });

            var result = BSTTester.IsBST(tree);

            Assert.Equal(result, false);
        }
    }

    public class Node
    {
        public int Value;
        public List<Node> Children;

        public Node(int value) : this(value, null) { }

        public Node(int value, List<Node> children)
        {
            this.Value = value;
            this.Children = children;
        }
    }
}