C++ Code

Friday, February 14, 2014

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.

Wednesday, January 29, 2014

Implementing Counting sort C++

Counting sort is a technique which sorts input in o(n) time complexity if it falls in particular range.
As the input falls in particular range, the counting method works well and can be rearranged easily.

Counting sort maintain count of each element appearing in the input then it places those in the order.

Code below sorts the input array A and returns B as a sorted array. Even you can choose to return sorted data in same array by copying B data to input array.

typedef vector<int> IntVect;
void CountingSort(IntVect & A, IntVect & B, int range)
{
   IntVect temp;

   for (size_t i = 0; i < range; i++)
   {
       temp.push_back(0);
   }

   for (int i = 0; i < A.size(); i++)
   {
       temp[A[i]] += 1;
   }

   for (int i = 1; i < temp.size(); i++)
   {
       temp[i] += temp[i - 1];
   }

   for (int i = 0; i < A.size(); i++)
   {
       B[temp[A[i]] - 1] = A[i];
       temp[A[i]] -= 1;
   }
}

Counting sort described here takes o(n) additional space.