Puddle of Riddles!

Sudoku Solver!

2013-01-23T21:26:00.003-08:00

Solution: Below is the code to solve a sudoku.

/*
Input Matrix:
 7  0  0  1  0  0  0  0  0 
 0  2  0  0  0  0  0  1  5 
 0  0  0  0  0  6  3  9  0 
 2  0  0  0  1  8  0  0  0 
 0  4  0  0  9  0  0  7  0 
 0  0  0  7  5  0  0  0  3 
 0  7  8  5  0  0  0  0  0 
 5  6  0  0  0  0  0  4  0 
 0  0  0  0  0  1  0  0  2 
*/

#define TRUE 1
#define FALSE 0
#define N 9
int S[N+1][N+1] = {0,};

void printMat(int S[][N+1])
{
    int i = 0;
    int j = 0;


    for(i=1; i<=N; i++) {
        for(j=1; j<=N; j++) {
            printf("%2d ", S[i][j]);
        }
        printf("\n");
    }
}

void initMat(int S[][N+1])
{
    S[1][1] = 7;
    S[1][4] = 1;

    S[2][2] = 2;
    S[2][8] = 1;
    S[2][9] = 5;

    S[3][6] = 6;
    S[3][7] = 3;
    S[3][8] = 9;

    S[4][1] = 2;
    S[4][5] = 1;
    S[4][6] = 8;
    
    S[5][2] = 4;
    S[5][5] = 9;
    S[5][8] = 7;

    S[6][4] = 7;
    S[6][5] = 5;
    S[6][9] = 3;

    S[7][2] = 7;
    S[7][3] = 8;
    S[7][4] = 5;

    S[8][1] = 5;
    S[8][2] = 6;
    S[8][8] = 4;

    S[9][6] = 1;
    S[9][9] = 2;
}

int permitted(int S[][N+1], int i, int j, int a)
{
    int x;

    for(x=1; x<=N; x++) {
        if(S[i][x] == a) {
            return FALSE;
        }
    }

    for(x=1; x<=N; x++) {
        if(S[x][j] == a) {
            return FALSE;
        }
    }

    return TRUE;
}

void solve(int S[][N+1], int i, int j)
{
    int a = 0;

    /*
     * this row is filled, jump to next row
     */
    if(j > N) {
        j = 0;
        i++;
    }

    /*
     * all rows are filled, print sol. and exit
     */
    if(i > N) {
        printMat(S);
        printf("\n");
        exit(0);
    }

    /*
     * each cell can take a value belonging to [1,9]
     */
    for(a=1; a<=N; a++) {
        /*
         * cell is already occupied, move to next cell
         */
        if (S[i][j]) {
            solve(S, i, j+1);
            return;
        }
        else if (permitted(S, i, j, a)) {
            S[i][j] = a;
            solve(S, i, j+1);
            S[i][j] = 0;
        } else {
            continue;
        }
    }
}

int main()
{
    initMat(S);
    printMat(S);
    printf("\n");
    solve(S, 1, 1);
}

Knapsack Problem

2013-01-21T16:25:00.001-08:00

Solution: Below is the code using dynamic programming,

#define MAX(a,b) (a)>(b)?(a):(b)
/*
 * Number of objects = 4
 * Capacity ig Knapsack = 8
 */
#define N 4
#define W 8
typedef struct {
    int32_t v;
    int32_t w;
} Object;

Object obj[N+1] = {{0, 0}, {15, 1}, {10, 5}, {9, 3}, {5, 4}};
int32_t V[N+1][W+1] = {0, };

int main()
{
    int32_t n = 0;
    int32_t w = 0;
    int32_t value = 0;
    int32_t weight = 0;

    for(n=1; n<=N; n++) {
        for(w=0; w<=W; w++) {
            weight = obj[n].w;
            value = obj[n].v;

            /*
             * Cases:
             * - Last item is excluded from the final set: V[n-1][w]
             * - Last item is included in the final set: value + V[n-1][w-weight]
             *
             * Corner case:
             * - If weight > w, choose V[n-1][w]
             */
            if(w >= weight) {
                V[n][w] = MAX( V[n-1][w], value + V[n-1][w-weight] );
            }
            else {
                V[n][w] = V[n-1][w];
            }
        }
    }

    printf("Ans = %d\n", V[N][W]);
    return 0;
}

Determine direction of stack growth.

2012-04-13T22:45:00.000-07:00

Solution #1: The direction of stack growth depends on OS as well as on the architecture. Below is a program to detect the direction of stack growth,

void b(int* x)
{
    int y;

    //if address of y is less than address of x
    //then the direction is downwards, upwards otherwise
    if(&y < x)
        printf("Stack growing downwards.\n");
    else
        printf("Stack growing upwards.\n");
}

void a()
{
    int x;
    b(&x);
}

int main()
{
    a();
    return 0;
}

Subset sum problem.

2012-03-23T01:51:00.001-07:00

Problem Statement: Given a set of numbers A[1...n], find a subset which sums up to a given number S.

Solution #1: Below is the code using Brute-force approach. The complexity is O(2^n).

int subsetSum(int* A, int len, int sum)
{
    if(sum == 0)
        return 1;
    
    if((len < 0) || (sum < 0))
        return 0;

    return subsetSum(A+1, len-1, sum) || subsetSum(A+1, len-1, sum-A[0]);
}

Solution #2: A faster way to solve this problem is by using dynamic programming. Below is the equation and the code,

RES[i][j] : is '1' if there is a subset in set A[1...i] which sums up to 'j', '0' otherwise.

RES[i][j] = RES[i-1][j] | RES[i-1][j-A[i]]

int RES[100][100];

int subsetSumDyn(int* A, int len, int sum)
{
    int i,j;

    for(j=0; j<=sum; j++)
        RES[0][j] = 0;
    
    for(i=0; i<=len; i++)
        RES[i][0] = 1;

    for(i=1; i<=len; i++)
    {
        for(j=1; j<=sum; j++)
        {
            int index = j - A[i-1];
            if(index >=0)
                RES[i][j] = RES[i-1][j] | RES[i-1][index];
            else
                RES[i][j] = RES[i-1][j];
        }
    }

    return RES[len][sum];
}

int main()
{
    int A[] = {13, 21, 11, 14, 4, 5};
    int len = sizeof(A)/sizeof(int);

    printf("Subset sub: %d\n", subsetSumDyn(A, len, 32));
    return 0;
}

Maze Algorithm.

2012-03-22T22:16:00.002-07:00

Problem Statement: A mouse is at one corner of a maze and he has to reach the corner diagonally opposite to him. Write an algorithm to find the path through the maze. The maze is represented by a matrix of '0's and '1's where '1' denotes a path and '0' denotes a wall.

This problem can be solved using backtracking. Below is the code,

#define N 4

void printMaze(int maze[N][N])
{
    int i, j;

    for(i=0; i < N; i++)
    {
        for(j=0; j < N; j++)
            printf("%d ", maze[i][j]);
        printf("\n");
    }
}

void move(int maze[N][N], int sol[N][N], int x, int y)
{
    if((x == N-1) && (y == N-1))
    {
        sol[x][y] = 1;
        printMaze(sol);
        return;
    }

    if(x != N-1)
    {
        if(maze[x+1][y])
        {
            sol[x][y] = 1;
            move(maze, sol, x+1, y);
            sol[x][y] = 0;
        }
    }

    if(y != N-1)
    {
        if(maze[x][y+1])
        {
            sol[x][y] = 1;
            move(maze, sol, x, y+1);
            sol[x][y] = 0;
        }
    }
}

int main()
{
    int maze[N][N] = 
    {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {0, 1, 1, 1}
    };

    int sol[N][N] = {0,};

    move(maze, sol, 0, 0);
    return 0;
}

Edit Distance.

2012-03-21T16:38:00.007-07:00

Problem Statement: The edit distance between two words is the minimum number of letter insertions, letter deletions and letter substitutions required to transform one word into another. For e.g. edit distance between "food"and "money" is 4. Below is the equation and the code for the problem,

min[i, j] = MIN(min[i-1, j] + 1, min[i, j-1] + 1, min[i-1, j-1] + (A[i] != B[j]))

#define MIN(a, b) ((a)<(b))?(a):(b)

int min[100][100];

int editDistance(char* A, char* B)
{
    int n = strlen(A);
    int m = strlen(B);

    int i, j;

    for(i=0; i <= n; i++)
        min[i][0] = i;
    
    for(j=0; j <= m; j++)
        min[0][j] = j;

    for(i=1; i <= n; i++)
    {
        for(j=1; j <= m; j++)
        {
            min[i][j] = MIN(min[i-1][j] + 1, min[i][j-1] + 1);
            min[i][j] = MIN(min[i][j], min[i-1][j-1] + (A[i-1]!=B[j-1]));
        }
    }

    return min[n][m];
}

int main()
{
    char A[50] = {0, };
    char B[50] = {0, };

    sprintf(A, "%s", "food");
    sprintf(B, "%s", "money");

    printf("EDIT DISTANCE: %d\n", editDistance(A, B));
    return 0;
}

Given two strings, print all interleaving strings.

2012-03-20T22:58:00.002-07:00

Solution #1: Note that interleaving of two strings does not change the actual order of the characters within the two strings. For e.g.

str1 = "AB"
str2 = "MN"

So, in the output string, 'A' will always come before 'B' and 'M' will always come before 'N' .

Interleaving strings are,

ABMN
AMBN
AMNB
MABN
MANB
MNAB

void interleave(char* str1, char* str2, char* str, int len)
{
    int i=0;

    //if both input strings reach null, print final string and return
    if(str1[0] == '\0' && str2[0] == '\0')
    {
        printf("%s\n", str-len);
        return;
    }

    if(str1[0] != '\0')
    {
        str[0] = str1[0];
        interleave(str1+1, str2, str+1, len);
    }
    if(str2[0] != '\0')
    {
        str[0] = str2[0];
        interleave(str1, str2+1, str+1, len);
    }
}

int main()
{
    char* str1 = "AB";
    char* str2 = "MNO";

    //get length of input strings
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int len = len1+len2;

    //allocate memory for output string
    char* str = (char*)malloc(len+1);
    memset(str, 0, len+1);

    interleave(str1, str2, str, len);
    return 0;
}

Longest Increasing Subsequence problem.

2012-03-18T23:52:00.003-07:00

Problem Statement: Given an array of integers, determine the longest increasing subsequence (not necesarily contiguous).

Solution #1: Below is the equation and the code for the problem,

Equations:
LIS[i] = MAX( LIS[j] ) + 1; where 0 <= j < i and A[i] > A[j]

#define MAX(a, b) ((a)>(b))?(a):(b)

int LIS[1000];

int lis(int* A, int len)
{
    int i, j;
    int max;

    LIS[0] = 1;

    for(i=1; i < len; i++)
    {
        max = 0;
        for(j=0; j < i; j++)
        {
            if(A[i] > A[j])
                max = MAX(max, LIS[j]);
        }

        printf("max: %d\n", max);

        LIS[i] = max + 1;
    }

    return LIS[len-1];
}

int main()
{
    int A[] = {4, 3, 9, 4 ,1 ,6};

    printf("LIS: %d\n", lis(A, 6));
    return 0;
}

Longest common subsequence problem.

2012-03-18T01:47:00.001-07:00

Problem Statement: Given two character arrays, arr1[m] and arr2[n], determine a longest common subsequence among these two arrays.

Solution #1: A Brute force approach will take exponential time to solve this problem. We will use dynamic programming to solve it in O(mn) time and space. Below is the equation and the code for the problem,

LCS[i, j] = LCS[i-1][j-1] + 1 ; arr1[i] == arr2[j]
= MAX(LCS[i-1][j], LCS[i][j-1]) ; otherwise

#define MAX(a,b) ((a)>(b))?(a):(b)

int LCS[100][100];

int lcs(char* arr1, int len1, char* arr2, int len2)
{
    int i = 0;
    int j = 0;

    //LCS is 0 when arr2 is NULL
    for(i=0; i <= len1; i++)
        LCS[i][0] = 0;

    //LCS is 0 when arr1 is NULL
    for(j=0; j <= len2; j++)
        LCS[0][j] = 0;

    for(i=1; i <= len1; i++)
    {
        for(j=1; j <= len2; j++)
        {
            if(arr1[i] == arr2[j])
                LCS[i][j] = LCS[i-1][j-1] + 1;
            else
                LCS[i][j] = MAX(LCS[i-1][j], LCS[i][j-1]);
        }
    }

    int temp = LCS[len1][len2];

    return temp;
}

int main()
{
    char* arr1 = "adbcad";
    char* arr2 = "dbacd";

    printf("LCS: %d\n", lcs(arr1, strlen(arr1), arr2, strlen(arr2)));
    return 0;
}

Count bits in an integer.

2012-03-16T00:39:00.001-07:00

Solution #1: The most straightforward approach is to check each bit one by one. Here is the code,

int count1(int n)
{
    int count=0;

    while(n)
    {
        if(n&1)
            count++;

        n = n>>1;
    }

    return count;
}

Solution #2: The below code is an efficient version which improves the average time,

int count2(int n)
{
    int count=0;

    while(n)
    {
        count++;
        n = n&(n-1);
    }

    return count;
}

Coin denomination problem

2012-03-15T00:32:00.002-07:00

Problem Statement: You are given n types of coin denominations of values d1 < d2 < ... < dn (all integers). Give an algorithm which makes change for an amount of money C with as few coins as possible.

Solution #1: Let min[i] represents the minimum number of coins required to make the change 'i'. Now, minimum number of coins required to make change 'C' = min[C-dj] + 1, where d1 <= dj <= dn. Below is the code with comments,

#define INFINITY 99999

int min[1000] = {0, };


int coins(int* arr, int len, int c)
{
    int i,j;

    //initialize all elements with INFINITY i.e.
    //infinite coins needed to make ith change
    for(i=0; i<=c; i++)
        min[i] = INFINITY;

    //0 coins are needed to get 0 change!
    min[0] = 0;

    //1 coin is needed to get the change equal to
    //any of the available coins
    for(i=0; i < len; i++)
        min[arr[i]] = 1;

    for(i=0; i<=c; i++)
    {
        for(j=0; j < len; j++)
        {
            int index = i-arr[j];
            if(index < 0)
                continue;

            if(min[index]+1 < min[i])
                min[i] = min[index]+1;
        }
    }

    return min[c];
}

int main()
{
    int arr[] = {4, 5, 7};
    printf("COINS: %d\n", coins(arr, 3, 166));

    return 0;
}

Implement atoi().

2012-02-28T16:39:00.002-08:00

Solution #1: Here is the code,

int my_atoi(char* str)
{
    int len = strlen(str);
    int i;
    int isNegative = 0;
    int num = 0;

    if(str[0] == '-')
    {
        isNegative = 1;
        str++;
    }

    for(i=0; i < len; i++)
    {
        int curr = str[i] - '0';

        //if it is a digit then put it at the units place
        if((curr >=0) && (curr <= 9))
        {
            num = num*10 + curr;
        }
        else //if not a digit then break
            break;
    }

    if(isNegative)
        num = num*-1;

    return num;
}

int main()
{
    printf("%d\n", my_atoi("-123"));
    return 0;
}

Find second maximum value in an array efficiently.

2012-02-28T16:02:00.002-08:00

Solution #1: Sorting is one obvious way, but, there is another efficient way. Here is the code,

int secondMax(int* arr, int len)
{
    int max = 0;
    int sMax = 0;
    int i = 0;

    for(i=0; i < len; i++)
    {
        int curr = arr[i];

        if(curr > max)
        {
            sMax = max;
            max = curr;
        }
        else if(curr > sMax)
            sMax = curr;
    }

    return sMax;
}

int main()
{
    int arr[5] = {3, 2, 5, 1, 4};

    printf("Second Max: %d\n", secondMax(arr, 5));

    return 0;
}

Implement mask_and_set_bits()

2012-01-30T17:01:00.001-08:00

Solution #1: Given an integer 'value', a position 'pos', an integer 'n' and another integer 'bits'. Replace 'n' bits in 'value' starting at position 'pos' with 'bits'. Here is the code written for 32-bit architectures,

void mask_and_set_bits(unsigned int* val, unsigned int pos, unsigned int n, unsigned int bits)
{
    *val = (*val)&((0xFFFFFFFF << (pos+n))| ~(0xFFFFFFFF << pos));
    *val = *val|(bits << pos)&~((0xFFFFFFFF << (pos+n))|~(0xFFFFFFFF << pos));
}

Find 2 smallest numbers in an array efficiently.

2012-01-26T20:51:00.001-08:00

Solution #1: Here is the code,

void findMinTwo(int* arr, int len)
{
    int i;
    int min = INT_MAX;
           int sMin = INT_MAX;

    for(i=0; i < len; i++)
    {
        //if arr[i] is less them min, set min = arr[i]
        //and set sMin = min
        if(arr[i] < min)
        {
            sMin = min;
            min = arr[i];
        }
        //else if arr[i] is less then sMin, update sMin
        else if(arr[i] < sMin)
        {
            sMin = arr[i];
        }
    }

    printf("%d %d\n", min, sMin);
}

Given an array of 0s and 1s, segregate 0s on left and 1s on right side.

2012-01-26T13:05:00.001-08:00

Solution #1: Here is the code,

void segregate01(int* arr, int len)
{
    int start = 0;
    int end = len-1;

    while(start < end)
    {
        while((arr[start] == 0) && (start != end))
            start++;

        while((arr[end] == 1) && (end != start))
            end--;

        if(start < end)
        {
            swap(&(arr[start]), &(arr[end]));
        }
    }
}

Given a sorted array with duplicate elements, find the number of occurrences of x.

2012-01-25T22:43:00.001-08:00

Solution #1: We will use the modified binary search to solve this in O(log n) time. Here is the code,

int count(int* arr, int x, int start, int end)
{
    if(start > end)
        return;

    int mid = (start+end)/2;
    int cnt = 0;

    if(arr[mid] == x)
        cnt = 1 + count(arr, x, start, mid-1) + count(arr, x, mid+1, end);
    else if(arr[mid] > x)
        cnt = count(arr, x, start, mid-1);
    else
        cnt = count(arr, x, mid+1, end);

    return cnt;
}

Given an array with duplicates, find the minimum distance between given x and y.

2012-01-25T13:14:00.001-08:00

Solution #1: Below is the code with explanation in comments,

int minDistance(int* arr, int len, int x, int y)
{
    int prevIndex = -1;
    int min = INT_MAX;
    int i=0;
    int first;
    int second;
    int distance;


    for(i=0; i < len; i++)
    {
        if((arr[i] == x) || (arr[i] == y))
        {
            //first time encounter with x or y
            //'first' stores either x or y, depending on
            //which is encountered first
            if(prevIndex == -1)
            {
                first = (arr[i]==x)?x:y;
                second = (arr[i]==x)?y:x;
                prevIndex = i;
            }
            else
            {
                //if arr[i] is same as 'first', reset prevIndex
                if(arr[i] == first)
                    prevIndex = i;
                //if arr[i] is different from 'first', calculate distance
                else
                {
                    distance = i - prevIndex;
                    prevIndex = i;
                    min = MIN(min, distance);

                    //swap first and second
                    int temp = first;
                    first = second;
                    second = temp;
                }
            }
        }
    }
    return min;
}

int main()
{
    int arr[] ={2, 3, 4, 6, 6, 7, 5, 1, 4};

    int len = sizeof(arr)/sizeof(int);

    printf("MIN DISTANCE: %d\n", minDistance(arr, len, 4, 5));
    return 0;
}

Reverse bits of a byte.

2012-01-24T22:55:00.001-08:00

Solution #1. E.g.

00001001 ==> 10010000

Here is the code,

#define GET(n, x) ((n&(1<<x))>>x)
#define SET(n, x) (n|(1<<x))
#define RESET(n, x) (n&(~(1<<x)))

int reverseBits(unsigned char n)
{
    int temp = n;
    int start = 0;
    int end = 7;

    while(start < end)
    {
        int sbit = GET(n, start); //find start bit
        int ebit = GET(n, end); //find end bit
        
        //set end bit equal to start bit
        temp = sbit?SET(temp, end):RESET(temp, end);
        //set start bit equal to end bit
        temp = ebit?SET(temp, start):RESET(temp, start);

        start++;
        end--;
    }

    return temp;
}

Reverse a linked list.

2012-01-22T18:07:00.002-08:00

Solution #1: Iterative approach to reverse a linked list,

void itrReverse(struct node** head)
{
    if(*head == NULL)
        return;

    struct node* prev = NULL;
    struct node* curr = *head;
    struct node* next = curr->next;

    while(1)
    {
        curr->next = prev;

        if(next == NULL)
            break;

        prev = curr;
        curr = next;
        next = next->next;
    }

    *head = curr;
}

Solution #2: Recursive approach to reverse a linked list,

void recReverse(struct node** head)
{
    struct node* first;
    struct node* rest;

    if(*head == NULL)
        return;

    first = *head;
    rest = first->next;

    if(rest == NULL)
        return;

    recReverse(&rest);

    first->next->next = first;
    first->next = NULL;

    *head = rest;
}

A sorted array is rotated unknown number of times. Find the minimum in the array.

2012-01-22T13:03:00.001-08:00

Solution #1: A sorted array rotated unknown number of times will look something like this,

6, 7, 8, 9, 1, 2, 3, 4, 5

We will use modified binary search to find the minimum element in this array. Here is the code,

int findMin(int* arr, int start, int end)
{
    if(start == end)
        return arr[start];

    int mid = (start+end)/2;

    if(arr[mid] < arr[mid-1])
        return arr[mid];
    else if(arr[mid] < arr[end])
        return findMin(arr, start, mid-1);
    else if(arr[mid] > arr[end])
        return findMin(arr, mid+1, end);
}

Find diameter of a Binary Tree.

2012-01-21T16:46:00.001-08:00

Solution #1: Diameter of a tree is the maximum distance between its any two nodes. For e.g. consider the below tree,

5
/ \
2 9
/ \ /
1 4 7

Diameter: 5 (1-2-5-9-7 or 4-2-5-9-7)

Here is the code,

int height(struct node* root)
{
    if(root == NULL)
        return 0;

    int lh = height(root->left);
    int rh = height(root->right);

    return 1 + MAX(lh, rh);
}

int diameter(struct node* root)
{
    if(root == NULL)
        return 0;

    int lheight = height(root->left);
    int rheight = height(root->right);

    int ldia = diameter(root->left);
    int rdia = diameter(root->right);

    return MAX(1 + lheight + rheight, MAX(ldia, rdia));
}

Inorder traversal without recursion.

2012-01-21T15:59:00.001-08:00

Solution #1: We can use a stack to implement Inorder traversal without recursion. Here is the code,

void recInorder(struct node* root, stack& s)
{
    struct node* current = root;

    while(1)
    {
        if(current != NULL)
        {
            s.push(current);
            current = current->left;
        }
        else
        {
            if(!s.empty())
            {
                struct node* temp = s.top();
                s.pop();

                printf("%d ", temp->data);

                current = temp->right;
            }
            else
                break;
        }
    }

    printf("\n");
}

Construct a Binary Tree, given its Inorder and preorder.

2012-01-21T14:39:00.001-08:00

Solution #1: Consider the following tree,

5
/ \
2 7
/ \ /
1 4 6

Inorder: 1 2 4 5 6 7
Preorder: 5 2 1 4 7 6

Algorithm:
1. Take first element from Preorder (in this case 5) and find it in Inorder.
2. Elements on the left side of '5' (1 2 4) form the left subtree of '5' and similarly elements on the right side (6 7) form right sub tree.
3. Recursively select each element from Preorder and create its left and right subtrees from Inorder.

Here is the code,

struct node* create(int* in, int* pre, int inStrt, int inEnd)
{
    if(inStrt > inEnd)
        return NULL;

    int i;
    static int preIndex = 0;

    //create node from preOrder
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = pre[preIndex];

    //find node in inOrder
    for(i=inStrt; i<=inEnd; i++)
        if(in[i] == pre[preIndex])
            break;

    preIndex++;
    
    //recursively call create for the left and right
    //half of inOrder created by preOrder
    temp->left = create(in, pre, inStrt, i-1);
    temp->right = create(in, pre, i+1, inEnd);

    return temp;
}

Find maximum width of a Binary Tree.

2012-01-21T00:33:00.001-08:00

Solution #1: Maximum width of a tree is explained in the below e.g.

/ \

5 7

/ \ /

9 8 3

Width of level 1: 1

Width of level 2: 2

Width of level 3: 3

Therefore, maximum width: 3

We will first write a function to calculate the width at a given level and then will use this function to determine the maximum width of the tree. Here is the code,

int width(struct node* root, int level)
{
    if(root == NULL)
        return 0;

    if(level == 1)
        return 1;

    return width(root->left, level-1) + width(root->right, level-1);
}

int maxWidth(struct node* root)
{
    if(root == NULL)
        return 0;

    int maxW = 0;
    int curW = 1;
    int level=2;

    while(curW)
    {
        curW = width(root, level++);

        maxW = MAX(curW, maxW);
    }

    return maxW;
}