Validate Binary Search Tree Algorithm
The Validate Binary Search Tree Algorithm is a method used to determine whether a given binary tree is a valid binary search tree (BST) or not. A binary search tree is a binary tree data structure in which each node has at most two children, and the left child node is less than or equal to the parent node and the right child node is greater than the parent node. This property must hold true for all nodes in the tree. The algorithm checks if the given binary tree adheres to these constraints, ensuring that the tree is a well-formed binary search tree suitable for operations like searching, insertion, and deletion in optimal time complexity.
The algorithm for validating a binary search tree typically involves a depth-first traversal of the tree, checking each node against its lower and upper bounds during the recursion. The initial call to the recursive function is made with the minimum and maximum possible values for the root node. At each node, the algorithm checks whether the node's value falls within its specified bounds. If the node violates its bounds, the algorithm returns false; otherwise, it proceeds with the recursive calls for the left and right children, updating the bounds accordingly. The algorithm returns true when all nodes adhere to the binary search tree property, ensuring the binary tree is a valid binary search tree.
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode *root) {
if (root == NULL)
return true;
return valid(root->left, INT_MIN, root->val) &&
valid(root->right, root->val, INT_MAX);
}
bool valid(TreeNode *node, int start, int limit) {
if (node == NULL)
return true;
if (node->val >= limit || node->val <= start)
return false;
return valid(node->left, start, node->val) &&
valid(node->right, node->val, limit);
}
};
//
// Solution 2, O(1) space
//
class Solution {
public:
bool isValidBST(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
TreeNode *parent = NULL;
TreeNode *current = root;
bool flag = true;
while (current != NULL) {
if (current->left == NULL) {
if (parent && parent->val >= current->val)
flag = false;
parent = current;
current = current->right;
}
else {
TreeNode *left_right_most = current->left;
while (left_right_most->right && left_right_most->right != current)
left_right_most = left_right_most->right;
if (left_right_most->right == NULL) {
left_right_most->right = current;
current = current->left;
}
else {
if (parent && parent->val >= current->val)
flag = false;
left_right_most->right = NULL;
parent = current;
current = current->right;
}
}
}
return flag;
}
};
// http://fisherlei.blogspot.com/2012/12/leetcode-recover-binary-search-tree.html
