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.

Finding out if given arrays represent identical binary search tree (BST)

You are given two arrays of integers. You need to check if the binary search tree is generated out of two arrays considering first element as root, then will the trees be identical. You are not allowed to create the binary tree. 

The techniques is fairly simple. Just try to identify from root, left and right elements of every sub tree. E.g. in the array 5, 6, 3, 7, 2 
Root: 5 -> Left 3
Root: 5 -> Right 6 -> right 7
Root: 3 -> left 2
Root: 6 -> right 7

Follow this for both the arrays and check if the left and right element of every sub tree are in the same order if not both array can not generate the identical BST.

Code below demonstrate this technique.  

bool DoesGivenArraysRepresentIdenticalBST( vector<int> firstArray, vector<int> secondArray) {     if( firstArray.count() != secondArray.count() )         return false;     if( firstArray.size() <= 0)         return true;     //Check if the root of every sub tree is same     if( firstArray[0] != secondArray[0] )         return false;     if( firstArray.size() <= 1)         return true;     vector<int> left1;     vector<int> right1;     for(int i = 1; i < firstArray.size(); i++)     {         if( firstArray[0] < firstArray[i] )             right1.Add(firstArray[i]);         else             left1.Add(firstArray[i]);     }     vector<int> left2;     vector<int> right2;     for(int i = 1; i < secondArray.size(); i++)     {         if( secondArray[0] < secondArray[i] )             right2.Add(secondArray[i]);         else             left2.Add(secondArray[i]);     }     return DoesGivenArraysRepresentIdenticalBST( left1, left2 ) && DoesGivenArraysRepresentIdenticalBST( right1, right2 ); }