Implement the validateBinarySearchTree method that checks whether the given tree satisfies binary search tree rules.
The input contains a binary tree represented as an integer array tree in level-order format.
Your task is to check whether the tree is a valid binary search tree. In a valid BST, every value in the left subtree must be smaller than the current node, and every value in the right subtree must be greater than the current node.
The rule must be true for every node, not only for the root node.
Example 1
[2,1,3]3trueExample 2
[5,1,4,0,0,3,6]7falseExample 3
[1,1]2falseUse minimum and maximum allowed boundaries while checking each node.
For the root, there is no boundary. When moving to the left child, the current node value becomes the maximum allowed value. When moving to the right child, the current node value becomes the minimum allowed value.
If any node is not strictly inside its allowed range, return false. If all nodes satisfy the rule, return true.
Pseudocode:
function validateBinarySearchTree(tree, size):
return isValid(0, negativeInfinity, positiveInfinity)
function isValid(index, minValue, maxValue):
if index >= size or tree[index] is missing:
return true
value = tree[index]
if value <= minValue or value >= maxValue:
return false
leftValid = isValid(2 * index + 1, minValue, value)
rightValid = isValid(2 * index + 2, value, maxValue)
return leftValid and rightValid