Verify whether a given binary tree is binary search tree or not

There are many ways to find out whether given binary tree is binary search tree or not.

Simplest way to verify is to traverse the tree in in-order fashion, create an array of node values while traversing in-order. Now check if this array is sorted or not.

We will extend similar approach for our solution. Instead of creating a array, we will just use the last value during in-order traversal to verify if its less than the current node value. If yes then the tree is binary tree.

Code below implements the approach discussed.

struct TreeNode {     int data;     TreeNode * pLeft;     TreeNode * pRight; }; bool VerifyIfBST(TreeNode * pRoot, int & lastvalue) {     if (pRoot)     {         bool  bLeft = VerifyIfBST(pRoot->pLeft, lastvalue);         bool  bRoot = true;         if (lastvalue > pRoot->data)         {                 bRoot = false;         }         lastvalue = pRoot->data;         bool bRight = VerifyIfBST(pRoot->pRight, lastvalue);         return ( bLeft && bRoot && bRight);     }     else         return true; }

The function will return true if tree is empty or if tree is binary search tree.