In the previous post we solved a LeetCode problem that required us to create a height-balance binary search tree from a sorted array. In this problem we are going to look at another LeetCode problem. This time we are validating that a binary tree is a valid binary search tree.

## Problem

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.

## Solution

In order to solve this problem we do an in-order traversal of the binary tree updating a global minimum value as we go along. Once we find a node that is less than (or equal) the minimum we know it’s not a valid binary search tree since in-order traversal visits the nodes in ascending order. The time complexity of this algorithm is $$O(n)$$ while the space complexity is $$O(h)$$ where $$h$$ is the height of the tree. Here’s the code:

/**
* 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) {
var min = Int64.MinValue;
return CheckValidity(root, ref min);
}

private bool CheckValidity(TreeNode node, ref Int64 min){
if (node is null){
return true;
}

if (!CheckValidity(node.left, ref min)){
return false;
}

if (node.val <= min){
return false;
}

min = node.val;

return CheckValidity(node.right, ref min);
}
}


In this post we solved another LeetCode problem that required us to check if a binary tree is a valid binary search tree. Again, I used the code I submitted to LeetCode so there’s nothing on the GitHub repository. Till next time, thanks for reading and don’t hesitate to leave a comment below.

Tags:

Updated:
The text passage describes a problem statement and solution for validating a binary search tree. It includes a problem definition, a solution approach, and a code implementation. There are no mathematical questions or answers provided in the text.
no_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
In the previous post we solved a LeetCode problem that required us to create a height-balance binary search tree from a sorted array. In this problem we are going to look at another LeetCode problem. This time we are validating that a binary tree is a valid binary search tree.

## Problem

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.

## Solution

In order to solve this problem we do an in-order traversal of the binary tree updating a global minimum value as we go along. Once we find a node that is less than (or equal) the minimum we know it’s not a valid binary search tree since in-order traversal visits the nodes in ascending order. The time complexity of this algorithm is $$O(n)$$ while the space complexity is $$O(h)$$ where $$h$$ is the height of the tree. Here’s the code:

/**
* 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) {
var min = Int64.MinValue;
return CheckValidity(root, ref min);
}

private bool CheckValidity(TreeNode node, ref Int64 min){
if (node is null){
return true;
}

if (!CheckValidity(node.left, ref min)){
return false;
}

if (node.val <= min){
return false;
}

min = node.val;

return CheckValidity(node.right, ref min);
}
}


In this post we solved another LeetCode problem that required us to check if a binary tree is a valid binary search tree. Again, I used the code I submitted to LeetCode so there’s nothing on the GitHub repository. Till next time, thanks for reading and don’t hesitate to leave a comment below.

Tags:

Updated:
user
The text passage describes a problem statement and solution for validating a binary search tree. It includes a problem definition, a solution approach, and a code implementation. There are no mathematical questions or answers provided in the text.

TYPE: NO_QUESTION