98 Validate Binary Search Tree ✅¶

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.

Example 1: alt

Input: root = [2,1,3]
Output: true

Example 2: alt

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Other Examples:

[1, 1] => false
[5,1,4,3,6] => false

C# Solution¶

using System;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class TreeNode
  {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x)
    {
      val = x;
    }
  }

  public class ValidBST
  {
    private List<int> values;

    public ValidBST()
    {
      values = new List<int>();
    }

    public bool IsValid(TreeNode root)
    {
      if (root != null)
      {
        if (!IsValid(root.left)) return false;

        if (values.Count > 0 && values[values.Count - 1] >= root.val)
        {
          return false;
        }
        values.Add(root.val);

        if (!IsValid(root.right)) return false;
      }

      return true;
    }
  }
}
```'

C# Tests¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class ValidBSTTests
  {
    [Fact]
    public void ValidBSTTest()
    {
      var node = new TreeNode(2);
      node.left = new TreeNode(1);
      node.right = new TreeNode(3);
      var validBST = new ValidBST();
      Assert.True(validBST.IsValid(node));
    }


    [Fact]
    public void InvalidBSTTest()
    {
      var node = new TreeNode(5);
      node.left = new TreeNode(1);
      node.right = new TreeNode(4);
      node.right.left = new TreeNode(3);
      node.right.right = new TreeNode(6);
      var validBST = new ValidBST();
      Assert.False(validBST.IsValid(node));
    }
  }
}
```'