Given a Binary Tree, we have to validate whether it is a valid Binary Search Tree(BST) or not. Print true, if given Binary Tree is a valid BST else print false.
Let’s understand this problem better with an example
15 / \ 8 25 / \ / \ 4 12 20 30 It's is valid Binary Serach Tree 15 / \ 8 25 / \ / \ 4 19 20 30 It's not a valid BST, becacuse node 19 is voilating the property of BST
Algorithm
We know that the Inorder traversal of a Binary Search Tree(BST) is a sorted order of elements present in the tree. Hence we can do the inorder traversal of the above tree and store it in an array. Later we can check if the generated array is sorted or not.
This approach will run in O(N) time, but the space complexity of the above approach is also O(N), because of the additional array.
Space optimized approach
In the above approach, the generated array is actually unnecessary except for comparing if the current element is greater than the previous element.
Hence instead of storing all the elements in an array, we will keep track of previous element data value and check if the value of the current node is greater than the previous element or not.
If the current node value is greater than the previous element for all the elements, then it’s a valid BST, else it is not a valid BST.
valid_bst(tree, prev)
{
if(tree == NULL)
return true;
if(!valid_bst(tree->left, prev))
return false;
//if current element is less than previous node
// in inorder traversal than it is not a valid BST
if(tree->data < prev)
return false;
prev = tree->data;
if(!valid_bst(tree->right, prev))
return false;
return true;
}
Implementation of the above algorithm in CPP
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node *left;
Node *right;
public:
Node(int x){
data = x;
left = NULL;
right = NULL;
}
};
bool valid_bst(Node *tree, int *prev)
{
if(tree == NULL)
return true;
if(!valid_bst(tree->left, prev))
return false;
if(tree->data < *prev)
return false;
*prev = tree->data;
if(!valid_bst(tree->right, prev))
return false;
return true;
}
int main()
{
Node *tree = new Node(15);
tree->left = new Node(8);
tree->right = new Node(25);
tree->left->left = new Node(4);
tree->left->right = new Node(12);
tree->right->left = new Node(20);
tree->right->right = new Node(30);
int prev = 0;
int res = valid_bst(tree, &prev);
if(res == 0)
cout<<"false"<<endl;
else
cout<<"true"<<endl;
}
Output
Input: 15 / \ 8 25 / \ / \ 4 12 20 30 Output: true
Time Complexity
The time complexity of the above algorithm is O(N), where N is the number of nodes a given tree because we are going to traverse all the elements of a given tree to check if the tree is valid Binary Search Tree. The space complexity of the above algorithm is O(1) as we are strong only a previous node value in an integer variable.