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;
}
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;
}
Rank Tree
A ranked binary tree is a binary tree whose nodes have integer ranks, with leaves having rank zero and missing nodes having rank minus one. If x is a child, the rank di erence of x, x, is the rank of its parent minus the rank of x. The rank of a ranked tree is the rank of its root.
The following code is for an unbalanced Rank Tree i.e has a worst case of O(n^2) for sorted input. The worst case can be avoided by balancing the nodes. Also, we would need to set left_sum every time a rotation occurs.
#include <iostream>
using namespace std;
struct node
{
int value,left_size;
struct node *left;
struct node *right;
};
typedef struct node TreeNode;
TreeNode* createNode(int n)
{
TreeNode *temp = new TreeNode();
temp->value = n;
temp->left_size = 0;
return temp;
}
void add(TreeNode* &root, int n)
{
if(root==NULL)
root = createNode(n);
else if(n<root->value)
{
add(root->left,n);
root->left_size++;
}
else
add(root->right,n);
}
int getRank(TreeNode* root, int n)
{
if(root->value==n)
return root->left_size;
else if(n<root->value)
{
if(root->left==NULL) return -1;
else return getRank(root->left,n);
}
else
{
int right_rank = (root->right)?getRank(root->right,n):-1;
if(right_rank==-1) return -1;
return 1 + root->left_size + right_rank;
}
}
int main()
{
TreeNode* root = NULL;
int a[] = {11,7,13,5,15};
int size = sizeof(a)/sizeof(a[0]);
for(int i=0; i<size; i++)
{
add(root,a[i]);
}
for(int i=0; i<size; i++)
{
cout<<getRank(root,a[i])<<" ";
}
return 0;
}
AVL Rotation Logic
We only need to calculate the balance factors and check for the following cases
Left Left
Left Right
Right Right
Right Left
Treap
This algorithm performs well since a treap is a complete binary search tree
Algorithm
Algorithm
- Insert according to key(similar to BST insert)
- Rotate Clockwise/Anticlockwise according to the priority during insertion.
For more details see here.
#include<iostream>
using namespace std;
class Treap
{
class Node
{
public:
int key,priority;
Node *left;
Node *right;
};
Node* root;
void clockwiseRotate(Node* &x)
{
Node* temp = x->left;
x->left = temp->right;
temp->right = x;
x = temp;
}
void anticlockwiseRotate(Node* &x)
{
Node* temp = x->right;
x->right = temp->left;
temp->left = x;
x = temp;
}
Node* createNode(int key, int priority)
{
Node* temp = new Node;
temp->key = key;
temp->priority = priority;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void balance(Node* &x)
{
if(x->left!=NULL && (x->left->priority> x->priority))
{
clockwiseRotate(x);
}
else if(x->right!=NULL && (x->right->priority> x->priority))
{
anticlockwiseRotate(x);
}
}
void insert(Node* ¤t, int key, int priority)
{
if(current==NULL)
current = createNode(key,priority);
else if(current->key>key)
insert(current->left,key,priority);
else
insert(current->right,key,priority);
balance(current);
}
void print(Node* x)
{
if(x == NULL ) return;
print(x->left);
cout<<"("<<x->key<<","<< x->priority<<")"<<endl;
print(x->right);
}
bool search(Node* x, int key)
{
if(x==NULL) return false;
if(x->key==key) return true;
if(key<x->key) return search(x->left,key);
else return search(x->right,key);
}
void deleteNode(Node* &x,int key)
{
if(x == NULL ) return;
if(key<x->key) deleteNode(x->left,key);
else if (key>x->key) deleteNode(x->right,key);
else
{
if( x->left== NULL && x->right == NULL) x = NULL;
else if (x->left==NULL) x = x->right;
else if (x->right==NULL) x = x->left;
else
{
if (x->left->priority>x->right->priority) clockwiseRotate(x);
else anticlockwiseRotate(x);
deleteNode(x,key);
}
}
}
public:
Treap(int key, int priority)
{
root = createNode(key,priority);
}
void insert(int key, int priority)
{
insert(root,key,priority);
}
void print()
{
print(root);
}
void search(int key)
{
search(root,key);
}
void deleteNode(int key)
{
deleteNode(root,key);
}
};
int main()
{
Treap t(1,4);
t.insert(7,3);
t.insert(8,10);
t.insert(12,1);
t.print();
t.deleteNode(7);
t.deleteNode(1);
t.print();
return 0;
}
Generalized Voting
Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list.
The algorithm should run in linear time. (n >=0 )
You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don’t use standard linear time deterministic selection algo
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
void generalizedVoting(vector<int> v, int m)
{
int n = v.size();
unordered_map<int,int> h;
unordered_map<int,int>::iterator iter;
// Treat numbers as blocks of size m similar to the game tetris
// There are n/m blocks of size m
for(int i=0; i<n; i++)
{
iter = h.find(v[i]);
if(iter!=h.end())
{
iter->second++;
}
else
h.insert(pair<int,int>(v[i],1));
if(h.size()==m)
{
unordered_map<int,int>::iterator iter = h.begin();
while(iter!=h.end())
{
--(*iter).second;
if((*iter).second == 0)
h.erase(iter++);
else
iter++;
}
}
}
// Reset values in unordered map
for(iter = h.begin(); iter!=h.end(); iter++)
{
iter->second = 0;
}
// find exact count of numbers present in unordered map
for(int i=0; i<n; i++)
{
iter = h.find(v[i]);
if(iter!=h.end())
iter->second++;
}
// Remove numbers with frequency less than equal to n/m
for(iter = h.begin(); iter!=h.end(); iter++)
{
if(iter->second<=n/m)
h.erase(iter);
}
for(iter = h.begin(); iter!=h.end(); iter++)
{
cout<<iter->first<<" ";
}
}
int main()
{
//int arr[] = {5,6,7,8,10,10,10,10,10,10,4,4,4,4,4,1,1,1,1};
int arr[] = {4,3,3,2,1,2,3,4,4,7};
//int arr[] = {5,6,7,8,10,4,4,4,4,1,1,1};
int n = sizeof(arr)/sizeof(arr[0]);
vector<int> v(arr,arr+n);
int k = 4;
generalizedVoting(v,k);
return 0;
}
Project Euler Statistics
Ronzii's Blog 