Check if a tree is balanced

Code to check if the tree is balanced:

int maxDepth(struct Tree *node)
{
if(node == NULL) return 0;

int leftDepth = maxDepth(node->left);
int rightDepth = maxDepth(node->right);

return leftDepth > rightDepth ?
leftDepth + 1 : rightDepth + 1;
}

int minDepth(struct Tree *node)
{
if(node == NULL) return 0;

int leftDepth = minDepth(node->left);
int rightDepth = minDepth(node->right);

return leftDepth < rightDepth ?
leftDepth + 1 : rightDepth + 1;
}

bool isBalanced(struct Tree *node)
{
if(maxDepth(node)-minDepth(node) <= 1)
return true;
else
return false;
}

For complete code and other tree operations refer: click here

Lowest Common Ancestor

Lowest common ancestor of a two nodes in a tree:

Tree *lowestCommonAncestor(Tree *root, Tree *p, Tree *q)
{
Tree *left, *right;
if(root == NULL) return NULL;
if(root->left == p || root->left == q
|| root->right == p || root->right == q) return root;
else {
left = lowestCommonAncestor(root->left,p,q);
right = lowestCommonAncestor(root->right, p,q);
if(left && right)
return root;
else
return (left) ? left : right;
}
}

For other tree operations or complete code refer to : click here

PrintAllPaths of a BST

Code to print all path of a binary tree:

/* printing array */
void printThisPath(int path[], int n)
{
for(int i = 0; i < n; i++)
cout << (char)path[i] << " ";
cout << endl;
}

/* recursion routine to find path */
void pathFinder(struct Tree *node, int path[], int pathLength)
{
if(node == NULL) return;
path[pathLength++] = node->data;

/* Leaf node is the end of a path.
  So, let's print the path */
if(node->left == NULL && node->right == NULL)
printThisPath(path, pathLength);
else {
pathFinder(node->left, path, pathLength);
pathFinder(node->right, path, pathLength);
}
}

/*printing all paths :
Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work. */

void printAllPaths(struct Tree *root)
{
int path[100];
pathFinder(root,path,0);
}

For other tree operations or complete code refer to : click here

Check if a tree is a subtree of another tree

C++ program to check if the tree is a sub tree of another tree:
bool matchTree(Tree *r1, Tree *r2)
{
/* Nothing left in the subtree */
if(r1 == NULL && r2 == NULL)
return true;
/* Big tree empty and subtree not found */
if(r1 == NULL || r2 == NULL)
return false;
/* Not matching */
if(r1->data != r2->data)
return false;
return (matchTree(r1->left, r2->left) &&
matchTree(r1->right, r2->right));
}

bool subTree(Tree *r1, Tree *r2)
{
/*Big tree empty and subtree not found */
if(r1 == NULL)
return false;
if(r1->data == r2->data)
if(matchTree(r1, r2)) return true;
return (subTree(r1->left, r2) || subTree(r1->right, r2));
}

bool isSubTree(Tree *r1, Tree *r2)
{
/* Empty tree is subtree */
if(r2 == NULL)
return true;
else
return subTree(r1, r2);
}


For other tree operations or complete code refer to : click here

Mirror a Tree

Here is the recursive algorithm to mirror or swap the nodes:

/* change a tree so that the roles of the left
and right hand pointers are swapped at every node */
void mirror(Tree *r)
{
if(r == NULL) return;

Tree *tmp;
mirror(r->left);
mirror(r->right);

/* swap pointers */
tmp = r->right;
r->right = r->left;
r->left = tmp;
}

For other tree operations or complete code refer to : click here

Breadth First Algorithm

Breadth First Algorithm OR Level wise printing of a BST:

/* Breadth first traversal using queue */
void BreadthFirstTraversal(Tree *root)
{
if (root == NULL) return;
deque <Tree *> queue;
queue.push_back(root);

while (!queue.empty()) {
Tree *p = queue.front();
cout << p->data << " ";
queue.pop_front();

if (p->left != NULL)
queue.push_back(p->left);
if (p->right != NULL)
queue.push_back(p->right);
}
cout << endl;
}

 For other tree operations or complete code refer: click here

Size of a Binary Tree

Recursion algorithm to find out the size of a binary tree:

int treeSize(struct Tree *node)
{
if(node == NULL) return 0;
else
return treeSize(node->left) + 1 + treeSize(node->right);
} 

For other tree operations and complete code refer: click here

Find an element in a BST

Sample code to find an element in BST:

Tree* lookUp(struct Tree *node, char key)
{
if(node == NULL) return node;

if(node->data == key) return node;
else {
if(node->data < key)
return lookUp(node->right, key) ;
else
return lookUp(node->left, key);
}
}

For other tree operations and complete code refer to : click here

Convert a tree to array

Here is the simple code for converting a BST to array of numbers:

/* Converting a BST into an Array */
void TreeToArray(struct Tree *node, int a[]){
static int pos = 0;

if(node){
TreeToArray(node->left,a);
a[pos++] = node->data;
TreeToArray(node->right,a);
      }
}

For other tree operations and complete code refer to : click here

Maximum of a Tree

Here is the simple code for finding the maximum of a BST:

/* Tree Maximum */
Tree* maxTree(struct Tree *node)
{
while(node->right)
node = node -> right;
return node;
}

For Other Tree operations and complete code refer to : click here

Find Minimum value of a BST

Here is the simple code , that finds out the minimum of a tree:

/* Tree Minimum */
Tree* minTree(struct Tree *node)
{
if(node == NULL) return NULL;
while(node->left)
node = node -> left;
return node;
}

For other operations and complete code refer to : click here

Kth Smallest of a BST

Given a BST of numeric values, find out the Kth smallest of the tree.

/* create a new tree from a sorted array */
Node *addToBST(int arr[], int start, int end)
{
 if(end < start) return NULL;
 int mid = (start + end)/2;

 Node *r = new Node;
 r->data = arr[mid];
 r->left = addToBST(arr, start, mid-1);
 r->right = addToBST(arr, mid+1, end);
 return r;
}

void kthSmall(Node *root, int k)
{
    static int n=0;
    if(root == NULL)
    {
        return;
    }
    kthSmall(root->left,k);
    n++;
    if(n==k)
    {
        cout<<k<<"th min element is :"<<root->data<<endl;
        return;
    }
    kthSmall(root->right,k);
}

int main()
{
int a[]={1,2,3,4,5,6,7,8,9,10,15,20,25,30,35,50};
Node *root = addToBST(a,0,15);
kthLarge(root,4);
}

Kth Largest of a BST

Given a BST of numeric values, find out the Kth largest of the tree.

/* create a new tree from a sorted array */
Node *addToBST(int arr[], int start, int end)
{
 if(end < start) return NULL;
 int mid = (start + end)/2;

 Node *r = new Node;
 r->data = arr[mid];
 r->left = addToBST(arr, start, mid-1);
 r->right = addToBST(arr, mid+1, end);
 return r;
}

void kthLarge(Node *root, int k)
{
    static int n=0;
    if(root == NULL)
    {
        return;
    }
    kthLarge(root->right,k);
    n++;
    if(n==k)
    {
        cout<<k<<"th max element is :"<<root->data<<endl;
        return;
    }
    kthLarge(root->left,k);
}

int main()
{
int a[]={1,2,3,4,5,6,7,8,9,10,15,20,25,30,35,50};
Node *root = addToBST(a,0,15);
kthLarge(root,4);
}

Next palindrome of a given number

Given a number , find out the next palindrome. For example

if n is 179, next palindrome is 181
if n is 456, next palindrome is 464
if n is 497, next palindrome is 505

If the given no is palindrome, return the same number.

Solution:
1.Store all digits into an array in the same order as the input number.
2.Check the first digit with last digit(1's pos),
3.if they are same , do nothing
4. if first no is greater than the last number, then replace the last number(1's pos) with first number and check the resultant is palindrome
5. if first no is less than the last no(1's pos) then replace the last number with first and increment the next to last no(10's pos) by 1.If you get more than 10 when you add 1 , then carry forward to 100's pos digit.continue this till you reach the first number or you get no carry.

bool isPalin(int a[],int dig)
{
    int i=0;
    int j=dig;
    while(i<j)
    {
    if(a[i]!=a[j-1])
        return false;
    i++;
    j--;
    }
    cout<<"Next palindrome no :";
    for(int i=0;i<dig;i++)
    {
        cout<<a[i];
    }
    return true;
}

void reverse(int *a,int digits)
{
    int j=digits;
    for(int i=0;i<j;i++,j--)
    {
        int t=a[i];
        a[i]=a[j-1];
        a[j-1]=t;
    }
    cout<<"input no :"<<endl;
    for(int i=0;i<digits;i++)
    {
        cout<<a[i];
    }
}

void find(int a[],int dig)
{
    /*for(int i=0;i<dig;i++)
    {
        cout<<a[i];
    }*/
    int j=dig;
    j--;
    for(int i=0;i<=j;i++,j--)
    {
        if(a[i]==a[j])
        {
            //do nothing
        }
        else
            if(a[i]>a[j])
            {
                a[j]=a[i];
                if(isPalin(a,dig))
                break;
            }
            else
            {
                a[j]=a[i];
                int k=j;
                int l=1;
                int t=0;
                do
                {
                    t=a[k-l] +1;
                    a[j-l] = t%10;
                    t = t / 10;
                    l++;
                }while(t>0);
            if(isPalin(a,dig))
                break;
            else
                find(a,dig);
            }

    }
}
void nextpalin(int n)
{
    int *a=new int[10];
    int dig;
    for( dig=0;n>0;dig++)
    {
        a[dig]=n%10;
        n=n/10;
    }
    reverse(a,dig);
    find(a,dig);
}

How to restrict C++ objects creation/deletion

How can you stop the :

1.Creation of object : Make all constructors as private, this is the way singleton objects work.
  If any one calls creates a static or dynamic object they will get the compilation error.

2.Creation of objects only on stack : Overload the new operator in your class and make it private.

3.Assignment of object to another object : Make you assignment operator as private.

4. Destruction of the object : Make your destructor as private and over load the delete operator and make it as private.

STL : Things to remember

STL Benifits:
1.Code Reuse
2.Efficiancy and Fast
3.Accurate and less buggy
4.Simple code and readable
5.Standardized and helps in writing new libraries

Sequence Containers:

• Vector
• List
• DeQueue
• Array
• Forward List

 Associative Containers:

• Set
• Multi-Set
• Map
• Multi-Map

 Unordered Containers:

Vector Or List? :
Use vector

• When you have insertions and deletions at the end
• Accessing elements is a frequent randomly
• Dynamically grows

Use List

• Insertions and deletions any where in the list is required.
• Random accessing is not a frequent activity.

Iterators:
Random Access Iterator
Bi-Directional Iterator
Forward Iterator
Input Iterator
Const Iterator


Things to Remember:

1.Code Bloat : Template functions occupies own space for different types(Increases the object code)

2. For latest compilers square<int>(5) and square(5) are same. Where for class templates you have to explicitly specify the type.

3. template<class T> and template<typename T> are same.

4.Vector is dynamic array and can grow dynamically(its allocated on heap).

5. In  STL, .end() points to one element after the last element.

6.Accessing a container using iterator is faster and proper approach than using the subscript.

7.Forward list has only forward iterator

8. Once created , then size of the array can not be changed.

9.Associative containers are implemented using binary tree.

10. Associative containers are always sorted.

11.Set and Map holds no duplicate keys, where Multi-Set and Multi-Map can hold duplicate key.s

12.Keys can not be modified in associative containers.

13. Functor : Class + Function
    Overloads () operator and can maintain the state.

14. DO NOT use auto_ptr with STL containers as it transfers ownership , where as STL needs the elements to be copiable.

C++ Things to remember

1. Size of empty class is 1, compiler needs to distinguish better the classes.
2.Static variable part of class do not take part in size of the class.
3.Static Integer variables can be initialized in the class declaration
Class XYZ
{
private:
static const int n=10;
};
4.A static function can not be virtual : Static works on class without object where as virtual needs and instance to be created and works at runtime.
5.Avoid calling virtual functions from constructor, as they behave like non-virtual as the instance of the class/object creation is not yet completed.
6.Class with private destructor should be created only on heap : If you create an instance on stack, compiler will have no clue on how to call destructor as it is private.
7.Reference and Const variables should be initialized using member initialization list: This helps the initialization of these member at the tile of object creation.
8.Compiler generated functions are public and inline AND they will be created only if they are used some where in the code else compiler will not generate them.
9.Reference and Const can not be copied, so compiler will not generate assignment operator and forces the user to create an assignment operator if the class has const or reference members.
10. What happens if there is a default constructor in Base class and user tries to initialize using the default constructor.

class Base
{
public:
Base(int a)
{
}
};

class Derived: public Base
{
public:
void display()
{
}
};

Derived obj; //Compiler Error

Reason : Default Constructor calls base class default constructor and also default constructor of the members. If any of the default constructor is missing then compiler throws error.
 11.Assignment Operator is member by member copy, where as Copy constructor is member by member initialization.
12.Size of a class with virtual function is SizeOf(Class) + SizeOf(vPtr) = Class + 4
13.Following are NOT inherited from Base Class

• Constructor
• Destructor
• Assignment Operator
• Friends

 14.No Virtual constructors in C++ : C++ is a staitc typed language and needs to know the type of the object at the time of creation.
   Virtual constructor can be achieved using Factory Method Design Pattern.
15.You should not delete the variables that are created using placement new.You should delete the complete buffer once its no longer required.
16.Volatile variables are modified by some external system other than the current code. Like,

•  CPU clocks
•  Interrupt signals

 17.Static global variables have only local linkage and are accessible  only in the current file.
      Where as global(non-static) variables have external linkage and are accessible using extern keyword.
18.When dynamic_cast is applied on reference variable of a base(Not referring to derived object) then "bast_cast" exception will be thrown.If it is a pointer type then NULL will be returned.
19.VTable is created per class , VPtr is created per object.
20. Vptr Address : (int*) (&obj+0)
       VTable Address : (int*)*(int*)(&obj+0)
  Vptr is vtable starting address.

Maximum no of ways to make change for an amount

Max possible ways for Coin Change Problem:

Given set of n coins what is the maximum no of ways to make an amount P.

This problem can be solved using Dynamic programming, we need to find out the maximum no of ways for the amount less than P and add all of them.

Coins = {1,2,5}
Amount =4

C(i) = Sum(C(j)) 1<j<Sum


The idea is to add all possible ways using each denomination.
For Ex:

{1,2,5} are the denomination, then to make change of 4, we do the following

First to make a change of 1 using S[0], which 1.
To make change of 2 using 1 is 1
To make change of 3 using 1 is 1
To make change of 4 using 1 is 1
Now to make change of 1 using 2 is not possible
To make change of 2 using 2 is 1 and we add this to previous count using 1, so total solution to make amount of 2 is 2.
To make change of 2 using 2 is is 1, and this will add up to making amount of 2 using 2. So total ways is 2
To make change of 3 using 2 is 0, we can't get 3 using only 2, we need to use 1, {1,2} or {2,1}.
  So to make amount of 3 is only 1 way.
To make change of 4 using 2 is 1, total ways to make amount of 4 is 2.
int count( int S[], int m, int Sum ) {
    // table[i] will be storing the number of solutions for
    // value i. We need n+1 rows as the table is consturcted
    // in bottom up manner using the base case (n = 0)   
    int table[16];   
    // Initialize all table values as 0  
    memset(table, 0, sizeof(table));   
    // Base case (If given value is 0)   
    table[0] = 1;    
    // Pick all coins one by one and update the table[] values
    // after the index greater than or equal to the value of the 
    // picked coin  
    for(int i=0; i<m; i++) 
    {
    for(int j=S[i]; j<=Sum; j++)
    {
        table[j] += table[j-S[i]];
    }
    }
    return table[Sum];
}

Cutting a Rod for the Best Price

Problem : Given a rod of n units and the price for each lenght of the unit, what is the optimal way to cut the rod so that the price is maximum.

For ex:

i   :      1    2    3    4     5      6      7       8
=============================================================
V :        2    4    6    9    10      15    17      25


If we cut the rod with 1 unit length each of 8 units, then the price is 8.
If we cut the rod with 2 unit length each of 4 units , then the price is 20
If we cut the rod with two 1 units and three 2 unit length, then price is 17

Now, to cut 8 unit rod, we need to find out what is teh best value for B[8-i] + V(i), i<=8

So the solution is :

S[i] = Max { V(j) + S[i-j], for 0<=j<=i

S[1] = Max { S[0] + v(1)} = 0 + 2 = 2
S[2] = Max { S[0] + v(2), S[1] +v(1)} { 0 + 4, 2 + 2} = 4
S[3] = Max { S[0] + v(3) , S[1] + v(2) , S[2] + v(1)} = { 6, 2+4, 4+2 } = 6
S[4] = Max { S[0] + v(4), S[1] + V(3), S[2] + v(2) , S[3] + v(1) = { 9,2+6,4+4,6+2} = 9
...
...
S[8]= 19  For 1,7 combination (2 + 17 ) = 19

C++ Program to Solve the above problem using dynamic programming:
void CutRod(int B[],int n)
{
    int S[9];

    for(int i=0;i<=n;i++)
        S[i]=INT_MIN;

    S[0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {                     //S[0]=0, S[1]=1
            if(S[i]<S[i-j]+B[j-1])   //S[2] <S[1]+B[1] or S[2] < S[0] +B[2]
            {
                S[i]=S[i-j]+B[j-1];
            }

        }
    }

int max=0;
for(int i=1;i<=n;i++)
if(S[i]>max)
max=S[i];

cout<<" Best price is :"<<max<<endl;

}

Output is : 19

Size of virtual class in c++

What is the size of a class, if it is part of virtual inheritance?


#include<iostream>
using namespace std;

class base {
public:
  int arr[10];  
};

class b1:  virtual public base { };

class b2:  virtual public base { };

class derived: public b1, public b2 {};

int main(void)
{
  cout<<sizeof(derived)<<"    "<<sizeof(int)<<endl;;
  getchar();
  return 0;
}

Output : 48
If you do non-virtual inheritance then it is 80(two copies from b1 & b2)

But if we do virtual inheritence then we are getting 8 additional bytes, where are we are supposed to get 40(single copy).So from where these additional bytes are comming.?

Reason: Since the methods are virtual, compiler add 4 bytes from each b1,b2 for vptr(virtual pointer).

Longest Increasing sub sequence

Problem: The problem is identify the longest increasing sub-sequence in an array of numbers.

The solution to the problem is to first find out all the increasing sequences less that the
current no and find out the max out of it. Add +1 to include the current no.

For ex: 2,7,3,4,9,8,12

For no of 9, there are two increasing sequences which are less than current no.

1)2,7
2)2,3,4

So the increasing seq count for 9 is 2,3,4,9 (count is 4).

So for the increasing seq is

LIS(i) = Max { LIS(j) } + 1 for 1<j<i and A[i]>A[j];
       = 1 if No such j

2,7,3,4,9,8,12

Following are increasing sub sequences:

LIS 1 : 2,7,9,12
LIS 2 : 2,3,4,9,12
LIS 3 : 2,3,4,8,12

Note : LIS for single element is 1, single element is increasing sequence.

C++ Program:

void LIS(int A[],int n)
{
int LIS[8];

for(int i=0;i<n;i++)
LIS[i]=1;

for(int i=0;i<n;i++)
{
        //For Each a[i], check if there are  is a
        //increasing seq, whose value is more than
        //the curent seq value.

        //We are checking for all the no which are
        //less than i.
    for(int j=0;j<i;j++)
    {
        if(A[i]>A[j] && LIS[i]<LIS[j]+1)
        {
            //IF you find a any no on the left side
            //of the current and
            LIS[i]=LIS[j]+1;
        }
    }
}

int max=0;
for(int i=0;i<n;i++)
if(LIS[i]>max)
max=LIS[i];

cout<<" Longest seq is :"<<max<<endl;
}

Max Contigous subsequence sum

Given n numbers, find out i and j where 1<=i<=j<=n, where the sumof elements from i to j is maximum.


All positive : Sum of all elements.

All Negative : Minimum of all the values.

Solution : S(i)= Max {S(i-1)+A[i],A[i]}


Idea is to find the window that gives the maximum sum. We check
1.if previous sum + A[i] is more than A[i], if we so we add A[i]
2.Otherwise, we start from a[i] a new windows.

Eg: -2,-3,5,-1,-2,6,-3

S(1)=A[i] = -2
S(2)= Max{S(2-1)+A[2],A[2]}= Max{-2+-3,-3}=-3
S(3)= Max{S(3-1)+A[3],A[3]}= Max{-3+5,5}=5
S(4)= Max{S(4-1)+A[4],A[4]}= Max{5+-1,-1}=4  //We add -1 to +ve no expecting some +ve number in future
S(5)= Max{S(5-1)+A[5],A[5]}= Max{4+-2,-2}=2
S(6)= Max{S(6-1)+A[6],A[6]}= Max{2+6,6}=8
S(7)= Max{S(7-1)+A[7],A[7]}= Max{8+-3,-3}=5

Now loop through S[i] and return the max value, which is 8.

void maxSumsubSeq(int A[],int n)
{
int S[n];
S[0]= A[0];
int l=0;
int h=0;
for(int i=1;i<n;i++)
{
    if(S[i-1]+A[i]>A[i])
    {
        S[i]=S[i-1]+A[i];
        h=i;
    }
    else
    {
        S[i]=A[i];   //Start the window from current postion
        l=i;
        h=i;
    }
}
int max =0;
for(int i=0;i<n;i++)
{
if(S[i]>max)
max=S[i];
}

Singleton without synchronization block in Java - thread safe approach

One of the colleague suggested this approach of writing thread-safe code for creating singleton objects.

Class Singleton
{
Class Inner{
static Singleton instance = new Singleton();
}

Singleton getInstance()
{
return Inner.instance;
}
};

Endian-ness of the System

#include<iostream.h>
union
{
int a;
char b[4];
}obj;

int main()
{
obj.a=0x1;
cout<<obj.b[0]<<"    "<<obj.b[3]<<endl;
printf("%d    %d",obj.b[0],obj.b[3]);
}

Assignment operator - for not corrupting the state of object

If we have an object say a1 of type Array and if we have a line like a1 = a1 somewhere, the program results in unpredictable behavior because there is no self assignment check in the above code. To avoid the above issue, self assignment check must be there while overloading assignment operator. For example, following code does self assignment check.

// Overloaded assignment operator for class Array (with self

// assignment check)

Array& Array::operator = (const Array &rhs)

{

  /* SELF ASSIGNMENT CHECK */

  if(this != &rhs)

  {

    // Deallocate old memory

    delete [] ptr;

    // allocate new space

    ptr = new int [rhs.size];

    // copy values

    size = rhs.size;

    for(int i = 0; i < size; i++)

      ptr[i] = rhs.ptr[i];   

  } 

  return *this;

}

There is minor issue with above code. Even though we are doing self assignment 
check, there is a probability of corrupting the state of current/left
had side object.

We are doing 

delete[] ptr; //which is the member of Array class.

And then we are re-allocating the memory, what if there is a exception thrown
during allocation of memory?? BAD_ALLOW,NO_MEM?

To avoid such problems, first copy the ptr to local_ptr , allocate memory
 an then delete the old memory.

Array& Array::operator = (const Array &rhs)

{

  /* SELF ASSIGNMENT CHECK */

  if(this != &rhs)

  {
int *local_ptr = ptr;

    // allocate new space

    ptr = new int [rhs.size];

    // Deallocate old memory

    delete [] local_ptr;

    // copy values

    size = rhs.size;

    for(int i = 0; i < size; i++)

      ptr[i] = rhs.ptr[i];   

  } 

  return *this;

}