ANOOB BACKER Technical Blog: December 2006

C++ Programming - BST Level Order Printing

Q. Level Order traversal of Binary Search Tree

This will traverse the BST in levels and print the elements according to the level from left to right.

Node:


struct Node {
    Node *left;
    Node *right;
    int data;
    Node(int value) : data(value) 
    {
        left = right = NULL;
    }
};

Explaination:
This is a common solution.

The logic behind this we start of with a queue which is having the root node as the only entry in the queue. Then we starts traversing the queue till it become empty during which we will be pushing the node's left and right into the queue along with pop the first entry and printing its data value.

BinaryTree Class:


class BinaryTree {
 Node *root;

 void insert(Node **node, int data) 
 {
  if (  *node == NULL ) 
   *node = new Node(data);
  else {
   if ( data <= (*node)->data )
    insert(&((*node)->left),data);
   else
    insert(&((*node)->right),data);
  }
 }

 public:
 BinaryTree() : root(NULL) { }
 void insert(int data) 
 {
  insert(&root,data);
 }


 void levelorder() {
  std::queue levelq;

  levelq.push(root);
  while( levelq.size() > 0 ) {
   Node *cur = levelq.front();
   std::cout << cur->data << "  ";
   levelq.pop();
   if (cur->left)  levelq.push(cur->left);
   if (cur->right) levelq.push(cur->right);
  }
 }
};

Labels: C++

Posted by - at 7:11 am | 0 comments read on

C Programming - Removing Loop from a Linked List

Given a Linked List which has loop within it, remove the looping with minimum complexity.

Node:


struct NODE {
    int data;
    struct NODE *next;
}

Explanation:
If Linked List is as given below


1->2->3->4->5->6
          |_________|

What we are doing in this solutions is inserting an element who data element is known to us between every node, such that it looks like


1->B->2->B->3->B->4->B->5->B->6
                    |__________________|

So the before inserting after the node which is looping we are checking whether that node next to the next is B or not, thereby finding out the looping node.

Solution:


/* Function which removes Loop from LL */

void vRemoveLoop(Node *head1)
{
    Node *tmp;
    Node *tmp1 = NULL;
    for(tmp = head1; tmp!= NULL; tmp = tmp1) {
 Node *temp = (Node *) malloc(sizeof(Node));
 temp->data = (int) temp;
 temp->next = NULL;
 if( (tmp->next != tmp) && (tmp->next->next->data !=  (int) tmp->next->next) ) 
         temp->next = tmp->next;
     tmp->next = temp;
            tmp1 = temp->next;
    }

    for(tmp = head1; tmp!= NULL; tmp = tmp->next) {
        tmp1 = tmp->next;
        tmp->next = tmp->next->next;
        if (tmp1->next != NULL ) 
            tmp1->next = tmp1->next->next;
        else
            tmp1->next = NULL;
    }
}

Post in your comments!

Labels: C

Posted by - at 11:10 am | 0 comments read on

C Programming - Divisible By 3 or Not (continued)

Some more additions to my previous post C Programming - Divisible By 3 or Not.

Code:

1. A solution that I got as a comment to my previous post. Thanks Piyush!


struct NODE {
    bool returnValue;
    struct NODE *next;
} MOD3_LOOP[3];

bool DivBy3(int n)
{
    MOD3_LOOP[0].returnValue = TRUE;
    MOD3_LOOP[0].next = &MOD3_LOOP[1];

    MOD3_LOOP[1].returnValue = FALSE;
    MOD3_LOOP[1].next = &MOD3_LOOP[2];

    MOD3_LOOP[2].returnValue = FALSE;
    MOD3_LOOP[2].next = &MOD3_LOOP[0];

    NODE *iterator = &MOD3_LOOP[0];
    int val = n;

    while(val != 0) {
        for (int i = 0; i < (val & 0x03); i++)
            iter = iter->next;
        val = val>>2;
    }

    return (iter->returnValue);
}

2. Another One


int div3(int number)
{
 if ( number < 0 ) number = -number;
 while ( number > 2 ) {
   unsigned int odd  = number & 0xaaaaaaaa;  
   unsigned int even  = number & 0x55555555;  
   int count = 0;
   while(odd) {
     odd &= (odd-1);
     count++;
   }
   while(even) {
     even &= (even-1);
     count--;
   }
   if ( count < 0 ) count = -count;
   number = count;
 }
 return (number == 0);
}

Please post in your comments about these solutions.

Labels: C

Posted by - at 10:14 am | 0 comments read on

C Programming - Copy Linked List (including arbitrary pointer)

Given a Linked List of node structure as


struct Node {
    type element;
    Node *next;
    Node *arb;
};

You are asked to create an exact copy this linked list. Pointer arb points to an arbitrary node with in the Linked List.

Solution:

Suppose the original linked list is like
X1->X2->X3->....->NULL we are supposed to create another Linked List like Y1->Y2->Y3->....->NULL.
First we modify the Source Linked list to look like
X1->Y1->X2->Y2->X3->Y3->.....->NULL, during which we only copy the data element. In another loop we obtain the value of arb by considering the fact the Xn's arb's next will be Yn's arb. Then we reverse back the Source Linked list along with destination linked list to the orginal structure.

Code:


#include < iostream >
#define ARRAY 2,1,3,4,2,3,4,5,6,7,1
using namespace std;

typedef struct NODE {
    int data;
    struct NODE *next;
    struct NODE *arb;
} Node;


Node *head1 = NULL;
Node *head2 = NULL;

/* Create a Link List which has to be copied */
void vCreateLL(Node **head)
{
    int nArb[] = { ARRAY };
    Node *temp = NULL;
    int i;

    /* Creating LL and filling data element */
    for(i = 0; i < sizeof(nArb)/sizeof(nArb[0]); i++ ) {
        Node *tmp = (Node *) malloc(sizeof(Node));
        tmp->data = rand() % 10;
        tmp->arb = NULL;
        tmp->next = NULL;
        if(*head == NULL ) *head = tmp;
        else temp->next = tmp;
        temp = tmp;
    }

    /* Filling up arb with node location given in an array nArb */
    temp = *head;
    for(i = 0; i < sizeof(nArb)/sizeof(nArb[0]); i++ ) {
        Node *tmp = *head;
        for(int j = 0; j < nArb[i]; j++ ) {
            tmp = tmp->next;
            if ( tmp == NULL)
                tmp = *head;
        }
        temp->arb = tmp;
        temp = temp->next;
    }
}

/* Print the LL along with node pointed by arb */
void vPrintLL(Node *head)
{
    for(Node *tmp = head; tmp != NULL; tmp = tmp->next) {
        printf("[ %d->%d ] ",tmp->data,tmp->arb->data);
    }
    printf("\n");
}

/* Copy Function which copies the LL 
 *which starts with head1 to head2 
 */

void vCopyLL(Node *head1,Node**head2)
{
    Node *tmp;
    Node *tmp1 = NULL;
    for(tmp = head1; tmp!= NULL; tmp = tmp1) {
        Node *temp = (Node *) malloc(sizeof(Node));
        temp->data = tmp->data;
        temp->arb = NULL;
        temp->next = tmp->next;
        tmp->next = temp;
        tmp1 = temp->next;
        if ( *head2 == NULL )
            *head2 = temp;
    }

    for(tmp = head1; tmp!= NULL; tmp = tmp->next->next) 
        tmp->next->arb = tmp->arb->next;

    for(tmp = head1; tmp!= NULL; tmp = tmp->next) {
        tmp1 = tmp->next;
        tmp->next = tmp->next->next;
        if (tmp1->next != NULL ) 
            tmp1->next = tmp1->next->next;
        else
            tmp1->next = NULL;
    }
}

int main()
{
    vCreateLL(&head1);
    vPrintLL(head1);

    vCopyLL(head1,&head2);
    vPrintLL(head2);
    return 0;
}

Labels: C

Posted by - at 8:59 pm | 1 comments read on