Designing a Binary Search Tree Validation class

Many times we need to validate a Binary Search tree i.e. verifying its properties,

• Left subtree of each node contains the nodes with value less than the node’s value.
• Right subtree of each node contains the nodes with value greater than the node’s value.
• Moreover, left and right subtree of each node must be a Binary Search Tree

For more details on BST check : http://en.wikipedia.org/wiki/Binary_search_tree

Simple and effective solution :

Just iterate with In-Order Traversal and check all elements are in increasing order or not.

Implementation Detail:

Only Variable is required to keep track of the last maximum value. During in-order traversal while visiting each node just check its value is greater than last maximum value or not.
If its value is greater than last maximum value then its fine, otherwise change the internal state to false.
[showads ad=inside_post]
Another Point:

What should be the initial value of max ?

If tree node can contain negative values then use bool bStart variable to keep track of the first element in the list.
Once first element is traversed then only start checking the max value.
There is no need to check the max comparison for first node i.e. Left most node of the tree.

BST Validator class :

</p>
<p>class BSTValidator<br />
{<br />
	bool bResult;<br />
	int max;<br />
	bool bStart;<br />
public:<br />
	BSTValidator()<br />
	{<br />
		bStart = false;<br />
		max = 0;<br />
		bResult = true;<br />
	}<br />
	void inOrderTraverse(node * pRoot)<br />
	{<br />
		if(pRoot == NULL || bResult == false)<br />
			return;<br />
		inOrderTraverse(pRoot-&gt;pLeft);	</p>
<p>		if( (bStart) &amp;&amp; (pRoot-&gt;value &lt; max) )<br />
				bResult = false;					</p>
<p>		if(bStart == false)<br />
			bStart = true;</p>
<p>		max = pRoot-&gt;value;<br />
		inOrderTraverse(pRoot-&gt;pRight);<br />
	}<br />
	bool validate(node * pRoot)<br />
	{<br />
		bStart = false;<br />
		bResult = true;<br />
		inOrderTraverse(pRoot);<br />
		return bResult;<br />
	}<br />
};</p>
<p>

Usage Detail,

<br />
node * pRoot = createTree();<br />
BSTValidator validatorObj;<br />
validatorObj.validate(pRoot);<br />

Node Structure:

<br />
typedef struct node<br />
{<br />
	int value;<br />
	node * pLeft;<br />
	node * pRight;<br />
}node;<br />