Spiral Order Traversal in a Tree
void iterativeSpiralTraversal(TreeNode* root)
{
stack<TreeNode*> currentLevel, nextLevel;
currentLevel.push(root);
bool direction = 1;
while(!currentLevel.empty())
{
TreeNode* current = currentLevel.top();
currentLevel.pop();
if(current)
{
cout<<current->value<<" ";
if(direction)
{
if(current->left)
nextLevel.push(current->left);
if(current->right)
nextLevel.push(current->right);
}
else
{
if(current->right)
nextLevel.push(current->right);
if(current->left)
nextLevel.push(current->left);
}
}
if(currentLevel.empty())
{
cout<<endl;
swap(currentLevel,nextLevel);
direction = !direction;
}
}
}
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;
}
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;
}
Median in a stream of numbers
The brute force algorithm uses a vector and maintains a sorted list. In this case the complexity of adding an element is O(n). Therefore, for n elements, the worst case is O(n^2).
Instead we maintain 2 priority queues i.e minHeap, maxHeap. We keep adding the numbers in both such that the number of elements in the maxheap is at max 1 greater than number of elements in the minHeap. Maintaining this constraint, allows us to get the median in O(1) time. Also, insertion becomes O(logn). Therefore, overall complexity is O(nlogn).
#include <iostream>
#include <queue>
using namespace std;
void insert(priority_queue<int> &maxHeap,priority_queue<int,vector<int>, greater<int> > &minHeap, int n)
{
if(maxHeap.size()==minHeap.size())
{
if(!minHeap.empty() && n>minHeap.top())
{
maxHeap.push(minHeap.top());
minHeap.pop();
minHeap.push(n);
}
else
maxHeap.push(n);
}
else
{
if(n<maxHeap.top())
{
minHeap.push(maxHeap.top());
maxHeap.pop();
maxHeap.push(n);
}
else
minHeap.push(n);
}
}
double getMedian(priority_queue<int> maxHeap,priority_queue<int,vector<int>, greater<int> > minHeap)
{
int a = minHeap.size();
int b = maxHeap.size();
if(a==0 && b==0) return -1;
if((a+b)%2==0)
return (double)(minHeap.top() + maxHeap.top())/2;
else
return maxHeap.top();
}
int main()
{
priority_queue<int> maxHeap;
priority_queue<int,vector<int>, greater<int> > minHeap;
int a[] = {7,11,17,8,19,2,3,15,16};
int n = sizeof(a)/sizeof(a[0]);
for(int i=0; i<n; i++)
{
insert(maxHeap,minHeap,a[i]);
cout<<getMedian(maxHeap,minHeap)<<endl;
}
return 0;
}
Modular Exponentiation
long long modulo(long long a,long long b,long long c)
{
long long result=1;
for(int i=0; i<b; i++)
{
result = result*a;
result = result%c;
}
return result;
}
long long mulmod(long long a, long long b , long long c)
{
long long x=0,y=a%c;
while(b>0)
{
if(b & 1)
{
x = (x+y)%c;
}
y=(y*2)%c;
b>>=1;
}
return x%c;
}
long long modulo2(long long a,long long b,long long c)
{
long long y=a,x=1;
printf("%lld %lld %lld\n",b,x,y);
while(b>0)
{
if(b & 1)
{
x = mulmod(x,y,c);
}
y = mulmod(y,y,c);
b>>=1;
}
return x%c;
}
AVL Tree
Check out logic of AVL balancing here
#include<iostream>
using namespace std;
struct node
{
int key;
struct node *left;
struct node *right;
int height;
};
typedef struct node Node;
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
Node* newNode(int key)
{
Node* node = new Node;
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
return x;
}
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
return y;
}
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
Node* insert(Node* node, int key)
{
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
node->height = max(height(node->left), height(node->right)) + 1;
int balance = getBalance(node);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preOrder(Node *root)
{
if(root != NULL)
{
cout<<root->key<<" ";
preOrder(root->left);
preOrder(root->right);
}
}
int main()
{
Node *root = NULL;
root = insert(root, 15);
root = insert(root, 22);
root = insert(root, 35);
root = insert(root, 45);
root = insert(root, 55);
root = insert(root, 30);
/* The constructed AVL Tree would be
35
/ \
22 45
/ \ \
15 30 55
*/
preOrder(root);
return 0;
}
Finding duplicates in O(n)
Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.
Goal : To find these repeating numbers in O(n) and using only constant memory space.
#include <iostream>
using namespace std;
void duplicates(int a[], int n)
{
for (int i = 0; i < n; i++)
{
while(a[a[i]]!=a[i])
swap(a[a[i]],a[i]);
}
for (int i = 0; i < n; i++)
if (a[i] != i)
cout<<a[i]<<" ";
}
int main()
{
int x[] = {1, 2, 3, 1, 3, 0, 6};
int n = sizeof x / sizeof x[0];
duplicates(x, n);
return 0;
}
Project Euler Statistics
Ronzii's Blog 