The logic behind validating a binary search tree is :
Examples of a valid and invalid binary search trees.
Inorder traversal of valid binary search tree : 3 5 6 7 10. ( The numbers are in ascending order ) Inorder traversal of an invalid binary search tree : 3 5 7 6 10. ( The numbers are not in ascending order )
Time Complexity of validating a binary search tree with N nodes : O(N), as the in-order traversal visits each node of the binary search tree once, the time complexity is O(N).
C++ : Validating a binary search tree. Implemented in C++11
#include<iostream>
#include<vector>
using namespace std;
class Node {
public:
int data;
Node * left;
Node * right;
Node(int x) : data(x), left(NULL), right(NULL)
{}
};
class Tree {
public:
vector<int> order;
/* The in-order traversal of a valid binary search tree is always in increasing order (sorted) */
void InOrder(Node * node) {
if (node != NULL) {
InOrder(node->left);
order.push_back(node->data);
InOrder(node->right);
}
}
bool IsValidBST(Node * node) {
InOrder(node);
for (int i=1; i < order.size(); i++) {
if (order[i-1] > order[i])
return false;
}
return true;
}
};
int main() {
/* 2
/ \
1 3 */
Node * root1 = new Node(2);
root1->left = new Node(1);
root1->right = new Node(3);
Tree t;
if (t.IsValidBST(root1)) {
cout << "Tree is a valid binary search tree" << endl;
} else {
cout << "Tree is a not a valid binary search tree" << endl;
}
/* 5
/ \
1 6
/ \
7 8 */
Node * root2 = new Node(5);
root2->left = new Node(1);
root2->right = new Node(6);
root2->right->left = new Node(7);
root2->right->right = new Node(8);
if (t.IsValidBST(root2)) {
cout << "Tree is a valid binary search tree" << endl;
} else {
cout << "Tree is a not a valid binary search tree" << endl;
}
/* 1
/
1 */
Node * root3 = new Node(1);
root3->left = new Node(1);
if (t.IsValidBST(root3)) {
cout << "Tree is a valid binary search tree" << endl;
} else {
cout << "Tree is a not a valid binary search tree" << endl;
}
/* 10
/ \
5 15
/ \
6 20 */
Node * root4 = new Node(10);
root4->left = new Node(5);
root4->right = new Node(15);
root4->right->left = new Node(6);
root4->right->right = new Node(20);
if (t.IsValidBST(root4)) {
cout << "Tree is a valid binary search tree" << endl;
} else {
cout << "Tree is a not a valid binary search tree" << endl;
}
return 0;
}
Output of validating a binary search tree implemented in C++11
Tree is a valid binary search tree
Tree is a not a valid binary search tree
Tree is a not a valid binary search tree
Tree is a not a valid binary search tree