Tag: tree

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) <= (_root.Value)
            || (_root.Right?.Value ?? 0) > (_root.Value))
        {
            var listIncludingRootValue = new List<int>()
            {
                _root.Value.Value
            };

            var leftLegValid = NodeFollowsBSTContract(_root.Left, new List<int>(), new List<int>(listIncludingRootValue));

            var rightLegvalid = NodeFollowsBSTContract(_root.Right, new List<int>(listIncludingRootValue), new List<int>());

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

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

        bool isLessThanAllParentLargerValues = !parentLargerValues.Any()
            || parentLargerValues.Where(value => node.Value.Value <= value).Count() == parentLargerValues.Count;

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

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

        if (node.Left != null)
        {
            var updatedLargerValues = GenerateUpdatedLists(node.Value.Value, parentLargerValues);
            var updatedSmallervalues = new List<int>(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<int> GenerateUpdatedLists(int addValue, List<int> values)
    {
        var updatedValues = new List<int>(values)
        {
            addValue
        };

        return updatedValues;
    }
}