Validate BST (Binary Search Tree) using C++
Check whether the given Binary Tree is a BST (Binary Search Tree) or not
What is a BST?
BST is a binary tree in which all the elements to the left of the root are having lesser value than the value of the root and all the elements to the right of the root are having greater value than the root. And this property should be applicable to all the nodes.
Approach 1:
In this approach, we will use a property of BST, according to which, the inorder traversal of a BST is always sorted. So we will traverse the given tree using the inorder method and store the elements in a vector. Now we will traverse in the vector and if we get a[i]>a[i+1] at any moment, it means the vector is not sorted, thus the tree is not a BST. If the vector follows a[i]<a[i+1] for every element, the tree will be a BST.
Time Complexity:
for traversing tree: O(n)
for traversing vector: O(n)
Space Complexity:
for storing elements: O(n)
C++ code:
class Solution {
public:
void helper(TreeNode* root,vector<int>& ans){
if(root==NULL)return;
helper(root->left,ans);
ans.push_back(root->val);
helper(root->right,ans);
}
bool isValidBST(TreeNode* root) {
vector<int>ans;
helper(root,ans);
for(int i=0;i<ans.size()-1;i++){
if(ans[i]>=ans[i+1])return 0;
}
return 1;
}
};Approach 2:
In this approach, we will use the concept of range. we know that the value of any element in a BST will be always less than the value at its right and greater than the value at its left. So we will check the range of every element by giving its range.
suppose we want the range of root->right, so we know that it will be greater than the value of root and less than LONG_MAX.
Time Complexity:
for Traversing tree: O(n)
Space Complexity:
O(1)
C++ code:
class Solution {
public:
bool isValidBST(TreeNode* root) {
if(root==NULL)return 1;
return helper(root,LONG_MIN,LONG_MAX);
}
bool helper(TreeNode* root,long min,long max){
if(root==NULL)return 1;
if(root->val>=max || root->val<=min)return 0;
return helper(root->left,min,root->val) and helper(root->right,root->val,max);
}
};
Comments
Post a Comment