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

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