Assignment 7

Due 4/29

Verify Binary Search Tree

Definition: A binary search tress is a tree that may be empty. If not, then

§ every tree node has a key (value) which are distinct to each other. And

§ all the keys (if any) in the left subtree of the root are smaller than the key in the root; all the keys (if any) in the right subtree are larger than the key in the root.

§ The left and right subtrees of the root are also binary search trees.

1) Define a tree node using a template class, as the type of the key may be int, float, double and so on. The class should contain a destructor that given the pointer or reference to the root node, should be able to destruct the whole subtree with the current node as the root node.

2) Write a friend function to a tree node that can verify if the tree (with the corresponding node as root) is binary search tree or not.

Test it with the following tree: (only C should be a valid binary search tree)