Leetcode 98. Validate Binary Search Tree (BST) - C#

Coding Sep 01, 2020

Introduction

Given a binary tree, determine if it is a valid binary search tree (BST). Let's discuss more about some of the inputs.

    2
   / \
  1   3

Output: true

    5
   / \
  1   4
     / \
    3   6

Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Sample Inputs

Approach

We consider the approach to keep track of minimum and maximum values allowed for any node.
The program performs the in-order traversal and in each recursive call, minimum and maximum range is passed. The range checks whether the current node’s value is within the given range.

Example Use case [4, 2, 7, 1, 5, 0, 9]
Main Code that calls the Util method with Min and Max initialised to null
THe main logic that verifies that the value is in a valid range
The stack diagram of how the flow would be, red circles denotes the failure cases
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool IsValidBST(TreeNode root) {
        return IsValidBstUtil(root, null, null);
    }
    
    private bool IsValidBstUtil(TreeNode node, int? min, int? max) {
        if (node == null) {
            return true;
        }
        if ((min != null && node.val <= min.Value) || (max != null && node.val >= max.Value)) {
            return false;
        }
        return IsValidBstUtil(node.left, min, node.val) && 
                IsValidBstUtil(node.right, node.val, max);
    }
}
C# Program to validate the BST