Given a binary tree we want to check if the tree is binary search tree or not
Example:
[5,2,9,null,null,3,10] is not a valid BST since 3 is less than the root value 5.
whereas
[5,2,9,null,null,8,10] is a valid BST.
Solutions:
To solve this problem we want to use dynamic programing using recursion.
What we are going to do is we validate the left and right side of the tree at each node level and see if it passes.
At each node, we will set a minimum and maximum value that we need to validate. Each node has to be greater than the minimum value we set and less than the maximum value and the min and max value changes for every node as we go down the tree using DFS (depth first search).
Initially we can assume the min is smallest double (Double.MinValue) and max is the biggest double number (Double.MaxValue).
When we recursively check if the node we are at is at the correct position, we do two things:
- If we are drilling down to the left side of the tree, then we pass the parent node as a max value and we don't care about the min value as long as it is greater than Double.MinValue.
- If we are drilling down to the right side of the tree, then we pass the parent node as a min value and we don't care about the max value as long as it is less than Double.MaxValue.
We check the above two things then we are good to go. Here is the code:
public bool IsValidBST(TreeNode root) {
if(root == null) return false;
if(root.left==null && root.right == null) return true;
return ValidateBSTHelper(root,Double.MinValue,Double.MaxValue);
}
public bool ValidateBSTHelper(TreeNode n, double min, double max) {
if(n==null) return true;
if(n.val <= min ) return false;
if(n.val >= max) return false;
return ValidateBSTHelper(n.left, min, n.val) && ValidateBSTHelper(n.right, n.val, max);
}