verify that a binary tree is a binary search tree

#include <iostream>
#include <iomanip>
#include <stack>
#include <conio.h>

/*
given a tree, verify that it is a valid binary search tree

- simple recursive verification of the roots of left and right sub trees
won\'t suffice as this fails for the following tree
- it requires that all the elements in the left sub-tree to be < root and 
all the elements in the right sub tree be > root. 

          6
           /  \\
      5     8
    /   \\  /  \\
   3    7 1   2
*/

struct Node
{
    Node(int x):data(x), left(0), right(0){}
    int data;
    Node* left, *right;
};

/*
verifyBST - verifies that the binary rooted at root is a BST

ancestor = value of the current root node when visiting the
corresponding left and right nodes

left = is a left subtree ? relative to the current root

For the root of the complete tree, values are default-ed
*/
bool verifyBST(Node* root, int ancestor = -1, bool left = true)
{
    if(root->left == NULL && root->right == NULL) // leaf node
        return true;
    
    // straight forward violation
    if(root->data < root->left->data ||  root->data > root->right->data)
        return false;
    
    if(ancestor != -1)
    { // not the root of the tree
        if(left)
        { // left subtree
            if(root->left->data > ancestor || root->right->data > ancestor)
                return false;
        }
        else
        { // right subtree
            if(root->left->data < ancestor || root->right->data < ancestor)
                return false;            
        }
    }
    
    if(root->left != NULL) 
    {
        if(!verifyBST(root->left, root->data, true))
            return false;
    }
    
    if(root->right != NULL) 
    {
        if(!verifyBST(root->right, root->data, false))
            return false;
    }
    
    // done, all is well !
    return true;
}

void testA()
{
    Node* root = new Node(3);
    root->left = new Node(1);
    root->right = new Node(4);
    assert(verifyBST(root) == true); 
}

void testB()
{
    Node* root = new Node(3);
    root->left = new Node(1);
    root->right = new Node(2);
    assert(verifyBST(root) == false); 
}

void testC()
{
    Node* root = new Node(7);
    root->left = new Node(5);
    root->right = new Node(8);
    root->left->left = new Node(3);
    root->left->right = new Node(6);
    root->right->left = new Node(10);
    root->right->right = new Node(12);
    root->left->right->left = new Node(30);    
    root->right->right->left = new Node(3);    
    assert(verifyBST(root) == false);
}

// not exhaustive ! but gives some confidence !!
void tests()
{
    testA();
    testB();
    testC();
}

int main()
{
    tests();
    getch();
}