Ronzii's Blog

Just your average geek's blog

Maximum Sum in a Tree

#include <iostream>
#include <climits>
using namespace std;
struct node
{
    int value;
    struct node *left;
    struct node *right;
};
typedef struct node TreeNode;
int treeMin = INT_MAX;
TreeNode* createNode(int n)
{
    TreeNode *temp = new TreeNode;
    temp->value = n;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
int max5(int a, int b,int c, int d, int e)
{
    return max(a,max(b,max(c,max(d,e))));
}
int maxSumTree(TreeNode* current, int* sum)
{
    if(current==NULL)
    {
        *sum = treeMin;
        return treeMin;
    }
    else
    {
        int ls = INT_MIN,rs = INT_MIN;
        int l = maxSumTree(current->left,&ls);
        int r = maxSumTree(current->right,&rs);
        *sum = max5(*sum,current->value, ls+rs+current->value,ls+current->value,rs+current->value);
        return max(*sum,max(l,r));
    }
}

void binaryTreeMin(TreeNode* current)
{
    if(current==NULL)   return;
    binaryTreeMin(current->left);
    if(treeMin>current->value)
        treeMin = current->value;
    binaryTreeMin(current->right);
}
int main()
{
    TreeNode* root = createNode(17);
    root->left = createNode(15);
    root->right = createNode(-20);
    root->left->left  = createNode(13);
    root->left->left->left  = createNode(-15);
    root->left->left->right  = createNode(-7);
    root->right->left  = createNode(50);
    root->right->right  = createNode(-72);
    binaryTreeMin(root);
    int sum = treeMin;
    cout<<maxSumTree(root,&sum);
    return 0;
}

March 31, 2012 Posted by | C++ | , , , , , | 1 Comment

Quick Select

Find the kth smallest element of an array using kth order statistic

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
int partition(int a[], int left, int right)
{
    int last = left;
    int key = a[left];
    for(int j=left+1; j<=right; j++)
    {
        if(a[j]<key)
        {
            last++;
            swap(a[last],a[j]);
        }
    }
    swap(a[left],a[last]);
    return last;
}
int findRank(int a[],int left, int right, int rank)
{
    int leftEnd  = partition(a,left,right);
    int leftSize = leftEnd - left + 1;
    if(leftSize==rank+1)
        return a[leftEnd];
    else if(rank<leftSize)
        return findRank(a,left,leftEnd-1,rank);
    else
        return findRank(a,leftEnd+1,right,rank-leftSize);
}
int main()
{
    srand(time(NULL));
    int a[] = {3,4,1,7,8,9,34};
    int n = sizeof(a)/sizeof(a[0]);
    for(int i=0; i<n; i++)
        cout<<findRank(a,0,n-1,i)<<" ";
    return 0;
}

March 31, 2012 Posted by | C++ | , , , | Leave a comment