LeetCode Link: 98. Validate Binary Search Tree
Language: C#
Problem Statement
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.
Examples
Example 1:
Input: root = [2,1,3]
Output: true
Example 2:
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.
Constraints
- The number of nodes in the tree is in the range [1, 104].
- -231 <= Node.val <= 231 - 1
Solution
/**
* 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;
* }
* }
*/
Approach 1
public class Solution
{
List<int> list = new List<int>();
public bool IsValidBST(TreeNode root)
{
Inorder(root);
for (int i=1; i<list.Count(); i++)
{
if (list[i-1] >= list[i])
{
return false;
}
}
return true;
}
private void Inorder(TreeNode root)
{
if (root is null)
{
return;
}
Inorder(root.left);
list.Add(root.val);
Inorder(root.right);
}
}
Approach 2
public class Solution
{
public bool IsValidBST(TreeNode root)
{
return Validate(root, null, null);
}
private bool Validate(TreeNode root, int? low, int? high)
{
if (root is null)
{
return true;
}
if ((low != null && low >= root.val) ||
(high != null && high <= root.val))
{
return false;
}
return Validate(root.left, low, root.val) &&
Validate(root.right, root.val, high);
}
}
Complexity
Time Complexity: O(N)
Space Complexity: O(N)