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

bst
Binary Search Tree

Simple and effective solution :

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

Advertisements

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 />

Do you want to Learn Modern C++ from best?

We have curated a list of Best C++ Courses, that will teach you the cutting edge Modern C++ from the absolute beginning to advanced level. It will also introduce to you the word of Smart Pointers, Move semantics, Rvalue, Lambda function, auto, Variadic template, range based for loops, Multi-threading and many other latest features of C++ i.e. from C++11 to C++20.

Check Detailed Reviews of Best Modern C++ Courses

Remember, C++ requires a lot of patience, persistence, and practice. So, start learning today.

Leave a Comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Scroll to Top