How Can I Modify a C++ BST Implementation to Check for Duplicate Values?

[FMAfan]

Homework Statement

I am working on an assignment in which I have to add a method to my BST class which checks if a binary tree object is in fact a Binary Search tree. So
(1) A left child must be smaller than the parent
(2) A right child must be larger than the parent
and:
(3) There cannot be any repeat data values

I think my code works for the first two conditions. What it does is check the root first against its maximum (right-most leaf) and minimum (left-most leaf) values. If that's true, then the method will call itself, checking that each subtree's parent is less than the right max value and and greater than the left min value.

However, this does not work correctly if a data value of the binary tree has been repeated.
I am completely stumped on how to also check for this case.

Homework Equations

bool isBST() --> sets initial min and max values to start check and calls second isBST method
bool isBST(Node<t>* r, int max, int min) --> checks to see if the < > rules have been followed

The Attempt at a Solution

//******************************************************************
// Function name: isBST
//*******************************************************************
template <class T>
bool BST<T> :: isBST() {
	Node<T>* seekerL = root,
		   * seekerR = root;
	T minimum,
	  maximum;

	if(!seekerL) { // if the tree is empty return true
		return true;
	} else { // find the left and right min and max values of the tree
		while(seekerL) {
			minimum = seekerL->key;
			seekerL = seekerL->left;
		}

		while(seekerR) {
			maximum = seekerR->key;
			seekerR = seekerR->right;
		}
	}

	// check that the tree and its subtrees follow the BST rules
	return isBST(root, minimum , maximum);
} // end isBST

//******************************************************************
// Function name: isBST
//*******************************************************************
template <class T>
bool BST<T> :: isBST(Node<T>* r, T min, T max) {
	Node<T> *parent = r;

	// if the parent has no children a leaf node has been reached
	if(!parent) {
		return true;
	}

	// if parent does not fall inbetween max or min return false
	if (parent->key < min || parent->key > max) {
		return false;
	}

	// else keep checking each subtree until rule is broken or tree is BST
	return (isBST(parent->left, min, parent->key) && isBST(parent->right, parent->key+1, max)); 
} // end isBST

Any help would be greatly appreciated. :)

Edit: Oh and the test data/key I am using is a Binary Tree of integers.

 

[FMAfan]

Never mind. I think I may have figured out another way to check my tree.

 

[Mene]

Hello,

Thank you for reaching out for help with your BST assignment. It seems like you have a good understanding of the basic rules for a BST and have implemented a solid solution for checking the first two conditions. However, you are correct in that your current solution does not account for repeated data values.

One way to handle this case would be to keep track of the values that have already been seen in the tree and check against that list as you traverse the tree. This could be done by creating a set or map data structure and adding each value to it as you traverse the tree. If a value is already in the set, then you know that the tree is not a valid BST.

Another approach could be to modify your current solution to keep track of the minimum and maximum values for each subtree as you traverse the tree. This way, if a repeated value is encountered, you can compare it to the minimum and maximum values for that subtree and determine if it follows the BST rules.

I hope this helps and good luck with your assignment!