Ronzii's Blog

Just your average geek's blog

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;
        }
    }
}

April 1, 2012 Posted by | C++, Data Structures | , , , , | 1 Comment

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

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;
}

March 30, 2012 Posted by | C++, Data Structures | , , , , | Leave a comment

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;
}

March 28, 2012 Posted by | C++, Data Structures | , , , , , | Leave a comment

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

March 28, 2012 Posted by | C++, Data Structures | , , , | 1 Comment

Binary Indexed Tree

Topcoder is a great resource for understanding it. See here.

#include <iostream>
#include <cstring>
using namespace std;
class bit
{
    int *tree;
    int maxVal;
public:
    bit(int N)
    {
        tree = new int[N+1];
        memset(tree,0,sizeof(int)*(N+1));
        maxVal = N;
    }
    void update(int idx, int val)
    {
        while (idx <= maxVal)
        {
            tree[idx] += val;
            idx += (idx & -idx);
        }
    }
    int read(int idx)
    {
        int sum=0;
        while (idx>0)
        {
            sum += tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }
    int readSingle(int idx)
    {
        int sum = tree[idx];
        if (idx > 0)
        {
            int z = idx - (idx & -idx);
            idx--;
            while(idx!=z)
            {
                sum-=tree[idx];
                idx-=(idx & -idx);
            }
        }
        return sum;
    }
};

int main()
{
    int a[] = {1,0,2,1,1,3,0,4,2,5,2,2,3,1,0,2};
    int n = sizeof(a)/sizeof(a[0]),MAX=65536,x;
    bit v(MAX);
    for(int i=1; i<=n; i++)
        v.update(i,a[i-1]);
    while (cin>>x)
        cout<<v.read(x)<<endl;
    return 0;
}

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

Iterative Traversal in a BST

void iterativeInorder(TreeNode* root)
{
    stack<TreeNode*> nodeStack;
    TreeNode* current = root;
    while (1)
    {
        while (current != NULL)
        {
            nodeStack.push(current);
            current = current->left;
        }
        if (nodeStack.size() == 0)
            return;
        current = nodeStack.top();
        nodeStack.pop();
        cout << current->value << " ";
        current = current->right;
    }
}
void iterativePreorder(TreeNode* root)
{
    stack<TreeNode*> nodeStack;
    TreeNode* current;
    nodeStack.push(root);
    while(!nodeStack.empty())
    {
        current = nodeStack.top();
        nodeStack.pop();
        if(current->right)
            nodeStack.push(current->right);
        if(current->left)
            nodeStack.push(current->left);
        cout<<current->value<<" ";
    }
}
void iterativePostorder(TreeNode* root)
{
    stack<TreeNode*> nodeStack;
    TreeNode* current = root;
    while(true)
    {
        while(current)
        {
            if(current->right)
            {
                nodeStack.push(current->right);
            }
            nodeStack.push(current);
            current = current->left;
        }
        if(nodeStack.empty())
        {
            return;
        }
        current = nodeStack.top();
        nodeStack.pop();
        if(current->right && !nodeStack.empty() && current->right==nodeStack.top())
        {
            nodeStack.pop();
            nodeStack.push(current);
            current = current->right;
        }
        else
        {
            cout<<current->value<<" ";
            current = NULL;
        }
    }
}

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