4
\$\begingroup\$

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;
    }
}
\$\endgroup\$
4
\$\begingroup\$

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 &= IsBinarySearchTree(_root.Left, _root.Value, Int.MIN_VALUE);
    valid &= 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 <= min || root.Value >= max)
      {
          return false;
      }
      return IsBinarySearchTree(root.Left, root.Value, min)
        && 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.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$
public int? Value { get; }

I really can't think of any situation where I would vant to store a null value in a search tree. But maybe I'm too narrow minded? What should the point be?

It is by the way impossible to set the value to null, because it is readonly and the only constructor takes not an int? but an int. So how would one could set a null value? And because you don't have a default constructor, you can't make a node without a value either.

In other words: you've made life a little more cumbersome by having a nullable value member on the node. Make it a normal int value.


In general validation is good and in a lot of situation it's necessary, but it's even better to not allow an invalid data structure in the first place. You can do that by making the constructor of BinaryTreeNode private and the Left and Right members private settable:

  public class BinaryTreeNode
  {
    public BinaryTreeNode Left { get; private set; }
    public BinaryTreeNode Right { get; private set; }

    public int? Value { get; }

    private BinaryTreeNode(int value)
    {
      Value = value;
    }
....

Then you just need a static method to create the root node:

    public static BinaryTreeNode Create(int value) => new BinaryTreeNode(value);

and a member method that inserts a new value:

public void Insert(int value)
{
  if (value <= Value)
  {
    if (Left == null)
      Left = new BinaryTreeNode(value);
    else
      Left.Insert(value);
  }
  else
  {
    if (Right == null)
      Right = new BinaryTreeNode(value);
    else
      Right.Insert(value);
  }
}

In this way, you're in full control of the data structure, and you never need to check is validity.


But if you insists on your approach, you can do it in the following way:

public bool IsValid()
{
  return (Left == null || this.Value >= Left.Value && Left.IsValid())
    && (Right == null || this.Value < Right.Value && Right.IsValid());
}

You don't need to collect any values, but only check if the value of the current node is greater than og equal to value of the left node and smaller than the value of right node.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I tunnel visioned on the possibility that a leg of a node could be null and erroneously extended that to the value as well. \$\endgroup\$ – IvenBach Jun 27 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.