Visual C++ - Binary Search Tree Validation - IsBinarySearchTree
The complete C++ source code for validating the binary search tree is given on this page.
All the nodes to left are less than the current node value and all nodes to the right are greater than the current node value. It would be true for each and every node in the binary search tree.
I have explained two algorithms for checking the validity of a binary search tree. Both methods are using recursive.
Source Code
// BST.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "windows.h"
#include <iostream>
typedef struct _BSTNode
{
struct _BSTNode *left;
struct _BSTNode *right;
int data;
} BSTNode;
BSTNode* NewNode(int data)
{
BSTNode *pNewNode = new BSTNode();
pNewNode->left = pNewNode->right = NULL;
pNewNode->data = data;
return pNewNode;
}
void PrintPostOrder(BSTNode *node)
{
if(node == NULL)
return;
PrintPostOrder(node->left);
PrintPostOrder(node->right);
std::cout << node->data << " ";
}
static BSTNode *root = NULL;
int MaxDepth(BSTNode *node)
{
if(node == NULL)
return 0;
int ldepth = MaxDepth(node->left);
int rdepth = MaxDepth(node->right);
int max = (ldepth > rdepth) ? ldepth : rdepth;
return (max + 1);
}
void PrintTree(BSTNode *node)
{
if(node == NULL)
return;
PrintTree(node->left);
//gotoxy(node->xpos, node->ypos);
std::cout << node->data << " ";
PrintTree(node->right);
}
BSTNode* Insert(BSTNode* node, int data)
{
if(node == NULL)
return NewNode(data);
if(data <= node->data)
{
if(node->left == NULL)
node->left = NewNode(data);
else
node->left = Insert(node->left, data);
}
else
{
if(node->right == NULL)
node->right = NewNode(data);
else
node->right = Insert(node->right, data);
}
return node;
}
BSTNode* Insert2(BSTNode* node, int data)
{
if(node == NULL)
return NewNode(data);
if(data <= node->data)
{
if(node->left == NULL)
{
node->left = NewNode(data);
}
else
if(node->right == NULL)
{
// Rearrange
int temp = node->data;
node->data = node->left->data;
node->right = node->left; // reuse valid left pointer
node->right->data = temp;
node->left = NewNode(data);
}
else
{
node->left = Insert2(node->left, data);
}
}
else
{
if(node->left == NULL) // left must be filled in first
{
// swap the values
int temp = node->data;
node->data = data;
data = temp;
// insert now
node->left = NewNode(data);
}
else
{
if(node->right == NULL)
node->right = NewNode(data);
else
node->right = Insert2(node->right, data);
}
}
return node;
}
int maxValueOfBST(BSTNode *node, int max = INT_MIN)
{
if(node == NULL)
return max;
if(node->data > max)
max = node->data;
max = maxValueOfBST(node->left, max);
max = maxValueOfBST(node->right, max);
return max;
}
int minValueOfBST(BSTNode *node, int min = INT_MAX)
{
if(node == NULL)
return min;
if(node->data > min)
min = node->data;
min = minValueOfBST(node->left, min);
min = minValueOfBST(node->right, min);
return min;
}
bool IsBinarySearchTree(BSTNode *node)
{
if (node == NULL)
{
return(true);
}
else {
if(node->left != NULL && node->data <= maxValueOfBST(node->left))
{
return false;
}
if(node->right != NULL && node->data >= minValueOfBST(node->right))
{
return false;
}
if(IsBinarySearchTree(node->left) == false ||
IsBinarySearchTree(node->right) == false)
{
return(false);
}
}
return true;
}
int IsBinarySearchTree(BSTNode * root, BSTNode **min, BSTNode **max)
{
BSTNode *minLeft, *minRight, *maxLeft, *maxRight;
if(root == NULL)
{
*min = NULL; *max = NULL; return(1);
}
if(!IsBinarySearchTree(root->left, &minLeft, &maxLeft))
return(0);
if(!IsBinarySearchTree(root->right, &minRight, &maxRight))
return(0);
if(maxLeft != NULL && root->data < maxLeft->data)
return(0);
if(minRight != NULL && root->data > minRight->data)
return(0);
if(minLeft != NULL) *min = minLeft; else *min = root;
if(maxRight != NULL) *max = maxRight; else *max = root;
std::cout << "Node : " << root->data << " Min: " << (*min)->data
<< " Max: " << (*max)->data << "\n";
return(1);
}
int _tmain(int argc, _TCHAR* argv[])
{
// 1st level
root = Insert(NULL, 60);
// 2nd level
Insert(root, 40);
Insert(root, 80);
// 3rd level
Insert(root, 30);
Insert(root, 50);
Insert(root, 70);
Insert(root, 90);
//Uncomment the following line to NOT make it a Binary Tree
//Insert(root->left->left, 100);
PrintTree(root);
std::cout << "\n";
PrintPostOrder(root);
std::cout << "\n";
std::cout << "Depth: " << MaxDepth(root);
std::cout << "\n\n";
BSTNode *l, *r;
// Method 1
if(IsBinarySearchTree(root, &l, &r) == true)
std::cout << "\nMethod1: is a BST\n";
else
std::cout << "\nMethod1: is NOT a BST\n";
// Method 2
if(IsBinarySearchTree(root) == true)
std::cout << "\nMethod2: is a BST\n";
else
std::cout << "\nMethod2: is NOT a BST\n";
return 0;
}
Output
30 40 50 60 70 80 90
30 50 40 70 90 80 60
Depth: 3
Node : 30 Min: 30 Max: 30
Node : 50 Min: 50 Max: 50
Node : 40 Min: 30 Max: 50
Node : 70 Min: 70 Max: 70
Node : 90 Min: 90 Max: 90
Node : 80 Min: 70 Max: 90
Node : 60 Min: 30 Max: 90
Method1: is a BST
Method2: is a BST
Press any key to continue . . .
|
|