LeetCode: Validate Binary Search Tree C#

Question

I was struggling with this question for many times, and I have solved it every time, because I understand the concept. but I can never get to a good concise solution which is easy to follow.

In a coding interview I always choke when I see this question.

This is the best solution I was able to come up with.

Can the code be written even more simple and easier to follow?

using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace TreeQuestions
{
    /// <summary>
    /// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/625/
    /// </summary>
    /// check the iterative version with a stack as well
    /// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/625/discuss/32112/Learn-one-iterative-inorder-traversal-apply-it-to-multiple-tree-questions-(Java-Solution)
    [TestClass]
    public class IsValidBSTtest
    {
        //   2
        //  / \
        // 1   3
        [TestMethod]
        public void ValidTree()
        {
            TreeNode root = new TreeNode(2);
            root.left = new TreeNode(1);
            root.right = new TreeNode(3);
            IsValidBSTclass temp = new IsValidBSTclass();
            Assert.IsTrue(temp.IsValidBST(root));
        }

        [TestMethod]
        public void NotValidTree()
        {
            TreeNode root = new TreeNode(5);
            root.left = new TreeNode(1);
            root.right = new TreeNode(4);
            root.right.left = new TreeNode(3);
            root.right.right = new TreeNode(6);
            IsValidBSTclass temp = new IsValidBSTclass();
            Assert.IsFalse(temp.IsValidBST(root));
        }

        /*
         *      10
         *      / \
         *     5   15
         *         /\
         *        6  20
         */


        [TestMethod]
        public void NotValidTree2()
        {
            TreeNode root = new TreeNode(10);
            root.left = new TreeNode(5);
            root.right = new TreeNode(15);
            root.right.left = new TreeNode(6);
            root.right.right = new TreeNode(20);
            IsValidBSTclass temp = new IsValidBSTclass();
            Assert.IsFalse(temp.IsValidBST(root));
        }
    }

    public class IsValidBSTclass
    {
        public bool IsValidBST(TreeNode root)
        {
            return Helper(root, null, null);
        }
        public bool Helper(TreeNode root, TreeNode minNode, TreeNode maxNode)
        {
            if (root == null)
            {
                return true;
            }
            if (minNode != null && root.val <= minNode.val || maxNode != null && root.val >= maxNode.val)
            {
                return false;
            }

            return Helper(root.left, minNode, root) && Helper(root.right, root, maxNode);
        }
    }
}

Answer 1

The main validation logic doesn't need "min node" and "max node", only the values. Passing the nodes as parameters adds complexity, because you have to handle null values, which would not be the case with simple integers. Being an unnecessary complexity (since nodes are not really needed), I suggest to eliminate it, for example:

public static bool IsValid(TreeNode root)
{
    if (root == null)
    {
        return true;
    }

    return IsValid(root.left, long.MinValue, root.val)
        && IsValid(root.right, root.val, long.MaxValue);
}

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

    if (node.val <= minVal || maxVal <= node.val)
    {
        return false;
    }

    return IsValid(node.left, minVal, node.val)
        && IsValid(node.right, node.val, maxVal);
}

Notice that I renamed the variable in the second method from root to node, since in this method the node is never the root. I would do the same in the original code, even though there it's sometimes really the root, but since that won't be the average case, I think that not calling it root may eliminate some confusion.

Lastly, making the helper method use long is necessary to support the (perhaps a bit naughty) input:

[-2147483648,null,2147483647]

Answer 2

For the most part I agree with your code. However there are a couple of things:

IsValidBST I think is redundant. Anyone running this method already knows it applies to a BST. I think just IsValid would be better.

Helper should have a better name, I think an IsValid overload would work and it should be private.

It doesn't make much sense to me to make an instance of this class. The methods don't rely on anything internal to the class. I would suggest making the methods static.

It could look something like this:

public class IsValidBSTclass
{
    public static bool IsValid(TreeNode root)
    {
        return IsValid(root, null, null);
    }
    private static bool IsValid(TreeNode root, TreeNode minNode, TreeNode maxNode)
    {
        if (root == null)
        {
            return true;
        }
        if (minNode != null && root.val <= minNode.val || maxNode != null && root.val >= maxNode.val)
        {
            return false;
        }

        return IsValid(root.left, minNode, root) && IsValid(root.right, root, maxNode);
    }
}

Answer 3

I don't like classes named …class. In languages including C#, it leads to expressions like new IsValidBSTclass(), not yielding a class.
I'd prefer BSTChecker over BSTValidator for the foreseeable bstValidator.isValid().