Validate BST

refer to : https://www.algoexpert.io/questions/Validate%20BST

1. 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 or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

2. Analysis.

10 10 is in (-inf, inf)

/ \

5 15. 5 is in (-inf, 10). maxValue = 10 15 is in (10, inf) minValue = 10

/ \ / \

2 5 13 22. 2 is in(minValue,5). 5 is in [5, 10). 13 is in (minValue, 15). 22 is in [15, maxValue)

3. code. O(n) time || O(d) space, d is the depth of the BST.

 1 class BST:
 2     def __init__(self, value):
 3         self.value = value
 4         self.left = None
 5         self.right = None
 6 
 7 
 8 def validateBst(tree):
 9     return helper(tree, float("-inf"), float("inf"))
10     
11 def helper(tree, minValue, maxValue):
12     if tree is None:
13         return True
14     if tree.value < minValue or tree.value >= maxValue:
15         return False
16     leftIsValid = helper(tree.left, minValue, tree.value)
17     return leftIsValid and helper(tree.right, tree.value, maxValue)

 1 import java.util.*;
 2 
 3 class Program {
 4   public static boolean validateBst(BST tree) {
 5     return helper(tree, Integer.MIN_VALUE,Integer.MAX_VALUE);
 6   }
 7     public static boolean helper(BST tree, int minValue, int maxValue){
 8         if(tree.value < minValue || tree.value >= maxValue){
 9             return false;
10         }
11         if(tree.left != null && !helper(tree.left, minValue, tree.value)){
12             return false;
13         }
14         if(tree.right != null && !helper(tree.right, tree.value, maxValue)){
15             return false;
16         }
17         return true;
18     }
19 
20   static class BST {
21     public int value;
22     public BST left;
23     public BST right;
24 
25     public BST(int value) {
26       this.value = value;
27     }
28   }
29 }