Data Structures and Algorithms 2065

A binary tree is a finite set of elements that are either empty or is partitioned into three disjoint subsets.

• The first subset contains a single element called the root of the tree.
• The other two subsets are themselves binary trees called the left and right sub-trees of the original tree.

Each element of a binary tree is called a node of the tree.                         

The following figure shows a binary tree with 9 nodes where A is the root.

Binary Search Tree

A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

• All keys in the left sub-tree of the root are smaller than the key in the root node
• All keys in the right sub-tree of the root are greater than the key in the root node
•  The left and right sub-trees of the root are again binary search trees

Example:

Given the following sequence of numbers,

        14, 4, 15, 3, 9, 14, 18

The following binary search tree can be constructed:

Following operations can be done in Binary Search Tree (BST):

• Search(k, T): Search for key k in the tree T. If k is found in some node of tree then return true otherwise return false.
• Insert(k, T): Insert a new node with value k in the info field in the tree T such that the property of BST is maintained.
• Delete(k, T):Delete a node with value k in the info field from the tree T such that the property of BST is maintained.
• FindMin(T), FindMax(T): Find minimum and maximum element from the given nonempty BST.

Recursion is a process by which a function calls itself repeatedly, until some specified condition has been satisfied. The process is used for repetitive computations in which each action is stated in terms of a previous result.

In order to solve a problem recursively, two conditions must be satisfied. First, the problem must be written in a recursive form, and second, the problem statement must include a stopping condition.

C program to find factorial of an integer:

#include<stdio.h>

#include<conio.h>

void main( )

{

clrscr( );

 int factorial(int);

 int n,f;

 printf("Enter the number: ");

 scanf("%d",&n);

 f=factorial(n);

 printf("Factorial of the %d number is %d",n,f);

 getch();

}

int factorial(int n)

{

  int f;

  if(n==1)

     return 1;

  else

     f=n*factorial(n-1);

     return f;

}

E.g.

A Fibonacci sequence is the sequence of integer in which each element in the sequence is the sum of the two previous elements.

Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.

       Fn = Fn-1 + Fn-2

E.g.

F8 = 0,  1,  1,  2,  3,   8,  13  or, F8 = 1,  1,  2,  3,  5,  8,  13,  21

Program to generate Fibonacci series up to n terms 

#include<stdio.h>

#include<conio.h>

void main()

{

int n, i;

int fibo(int);

printf("Enter n:");

scanf("%d",&n);

printf("Fibonacci numbers up to %d terms:\\n",n);

for(i=1;i<=n;i++)

printf("%d\\n",fibo(i));

getch();

}

int fibo(int k)

{

if(k == 0 || k == 1)

return k;

else

return fibo(k-1)+fibo(k-2);

}

Stack

A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of the stack. The deletion and insertion in a stack is done from top of the stack.

 It is a linear data structure which store data temporarily to perform PUSH and POP operation in LIFO (Last-In-First-Out) sequence.

Fig::A stack containing items or elements

Implementation of stack using array

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void push(int);

void pop();

void display();

int stack[SIZE], top = -1;

void main()

{

   int value, choice;

   clrscr();

   while(1){

      printf("\\n\\n***** MENU *****\\n");

      printf("1. Push\\n2. Pop\\n3. Display\\n4. Exit");

      printf("\\nEnter your choice: ");

      scanf("%d",&choice);

      switch(choice){

          case 1: printf("Enter the value to be insert: ");

                  scanf("%d",&value);

                  push(value);

                  break;

          case 2: pop();

                  break;

          case 3: display();

                  break;

          case 4: exit(0);

          default: printf("\\nWrong selection!!! Try again!!!");

      }

   }

}

void push(int value){

   if(top == SIZE-1)

      printf("\\nStack is Full!!! Insertion is not possible!!!");

   else{

      top++;

      stack[top] = value;

      printf("\\nInsertion success!!!");

   }

}

void pop(){

   if(top == -1)

      printf("\\nStack is Empty!!! Deletion is not possible!!!");

   else{

      printf("\\nDeleted : %d", stack[top]);

      top--;

   }

}

void display(){

   if(top == -1)

      printf("\\nStack is Empty!!!");

   else{

      int i;

      printf("\\nStack elements are:\\n");

      for(i=top; i>=0; i--)

          printf("%d\\n",stack[i]);

   }

}

E.g.

Queue

A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).

Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.

Implementation of Queue using array

#include<stdio.h>

#include<conio.h>

#define SIZE 10

void enQueue(int);

void deQueue();

void display();

int queue[SIZE], front = -1, rear = -1;

void main()

{

   int value, choice;

   clrscr();

   while(1){

      printf("\\n\\n***** MENU *****\\n");

      printf("1. Insertion\\n2. Deletion\\n3. Display\\n4. Exit");

      printf("\\nEnter your choice: ");

      scanf("%d",&choice);

      switch(choice){

         case 1: printf("Enter the value to be insert: ");

                scanf("%d",&value);

                enQueue(value);

                break;

         case 2: deQueue();

                break;

         case 3: display();

                break;

         case 4: exit(0);

         default: printf("\\nWrong selection!!! Try again!!!");

      }

   }

}

void enQueue(int value){

   if(rear == SIZE-1)

      printf("\\nQueue is Full!!! Insertion is not possible!!!");

   else{

      if(front == -1)

         front = 0;

      rear++;

      queue[rear] = value;

      printf("\\nInsertion success!!!");

   }

}

void deQueue(){

   if(front == rear)

      printf("\\nQueue is Empty!!! Deletion is not possible!!!");

   else{

      printf("\\nDeleted : %d", queue[front]);

      front++;

      if(front == rear)

         front = rear = -1;

   }

}

void display(){

   if(rear == -1)

      printf("\\nQueue is Empty!!!");

   else{

      int i;

      printf("\\nQueue elements are:\\n");

      for(i=front; i<=rear; i++)

         printf("%d\\t",queue[i]);

   }

}

E.g.

Two dimension (2D) array: 

A two-dimensional array is nothing but a matrix, that has rows and columns in it. For e.g.

    int a[3][4];

    float b[10][10];

Multidimensional array :

Any array which has a dimension higher than One is a multidimensional array. 2D array is also a multidimensional array.

E.g. of 3D array

    int a[3][2][4];

Here, the first subscript specifies a plane number, the second subscript a row number and the third a column number.

DIFFERENCE :

 Every 2D array is a multidimensional array but the other way round is not necessary(for example a 3D array is also a multidimensional array but its surely not 2D).

An algorithm is a sequence of unambiguous instructions used for solving a problem, which can be implemented (as a program) on a computer

Algorithms are used to convert our problem solution into step by step statements. These statements can be converted into computer programming instructions which forms a program. This program is executed by computer to produce solution. Here, program takes required data as input, processes data according to the program instructions and finally produces result as shown in the following picture

Algorithm to convert infix to postfix expression

1. Scan the infix string from left to right.

2. Initialize an empty stack.

3. If the scanned character is an operand, add it to postfix sting

4. If the scanned character is an operator, PUSH the character to stack.

5.  If the top operator in stack has equal or higher precedence than scanned operator then POP the operator present in stack and add it to postfix string else PUSH the scanned character to stack.

6. If the scanned character is a left parenthesis ‘(‘, PUSH it to stack.

7. If the scanned character is a right parenthesis ‘)’, POP and add to postfix string from stack until an ‘(‘ is encountered. Ignore both '(' and ')'.

8. Repeat step 3-7 till all the characters are scanned.

9. After all character are scanned POP the characters and add to postfix string from the stack until it is not empty.

Example:

Infix expression: A*B+C

Postfix expression: AB*C+

A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue).

Queue follows First-In-First-Out (FIFO) methodology, i.e. the first element inserted into the queue is the first element to be removed.

Post-order traversal is one of the multiple methods to traverse a tree. 

In Post-Order traversal, the root node is visited after left child and right child. In this traversal, left child node is visited first, then its right child and then its root node. This is recursively performed until the right most node is visited.

Algorithm:

E.g.

The post-order traversal output of the given above tree is: H I D E B F G C A

C function for post-order traversing:

Let pRoot is a given pointer to a root node of a binary tree. 

void post-order(BiNodeType *pRoot)

{

if(root!=NULL)

{

postorder(pRoot->left);

postorder(pRoot->right);

printf(“%d”, pRoot->info);

}

}

Sorting is the technique to arranging the items of list in any specific order which may be ascending or descending order. 

Insertion Sort

An algorithm consider the elements one at a time, inserting each in its suitable place among those already considered (keeping them sorted). Insertion sort is an example of an incremental algorithm. It builds the sorted sequence one number at a time.

Suppose a[0], a[1], a[2], …………….,a[n-1] are n elements in memory, insertion sort works as follow:

Pass 1: a[0] by itself is trivially sorted.

Pass 2: a[1] is inserted either before or after a[0] so that a[0], a[1] is sorted.

Pass 3: a[2] is inserted into its proper place in a[0],a[1], that is before a[0], between a[0] and a[1], or after a[1], so that: a[0],a[1], a[2] is sorted.

……

Pass n: a[n-1] is inserted into its proper place in a[0], a[1], a[2], ……….a[n-2] so that a[0], a[1], a[2], ……….a[n-1] is sorted array with ‘n’ elements.

Algorithm for Insertion Sort:

Let a[n] be an array of size n. 

Void insertionsort(int a[], int a)

{

          int i, j, temp;

         for(i=1;i<n;i++)

        {

              temp= a[i];

              j=j--;

            while((temp<a[j])&&(j>=0))

          {

            a[j+1]= a[j];

           j= j--;

       }

      a[j+1]=temp;

    }

}

Example:

A list of unsorted elements are: 9, 7, 6, 15, 16, 5, 10, 11

Binary search is an extremely efficient search technique that searches the given item in minimum possible comparisons in the already sorted list of given elements. The logic behind the technique is:

1. First find the middle element of the list

2. Compare the mid-element with searched item.

    There are three cases:

      a. If it is a desired element then search is successful.

      b. If it is less than desired item then search only in the first half of the list.

      c. If it is greater than desired item then search in the second half of the list.

Recursive Algorithm:

BinarySearch(A,l,r, key)

{

    if(l= = r)

    {

        if(key = = A[l])

            return l+1;         //index starts from 0

        else

            return 0;

    }

     else

    {

        m = (l + r) /2 ;

        if(key = = A[m])

                return m+1;

        else if (key < A[m])

                return BinarySearch(l, m-1, key) ;

        else

                return BinarySearch(m+1, r, key) ;

    }

}

Example:

Consider an array of data:

 21, 36, 56, 79, 101, 123, 142, 203

Now,

Tracing binary search for above data;

Set L=0, R=7, key=123 (search for 123)

Therefore, search successful and key(123) is at position (Mid+1)=5+1=6.

Pre-order Traversal 

In Pre-Order traversal, the root node is visited before left child and right child nodes. In this traversal, the root node is visited first, then its left child and later its right child. This pre-order traversal is applicable for every root node of all subtrees in the tree.

Algorithm:

.

E.g.

The preorder traversal output of the given above tree is: A B D H I E C F G

In-order Traversal:

In In-Order traversal, the root node is visited between left child and right child. In this traversal, the left child node is visited first, then the root node is visited and later we go for visiting right child node. This in-order traversal is applicable for every root node of all subtrees in the tree. This is performed recursively for all nodes in the tree

Algorithm:

E.g.

The inorder traversal output of the given tree is: H D I B E A F C G

Tower of Hanoi (TOH) is a mathematical puzzle which consists of three pegs named as origin, intermediate and destination and more than one disks. These disks are of different sizes and the smaller one sits over the larger one.

In this problem we transfer all disks from origin peg to destination peg using intermediate peg for temporary storage and move only one disk at a time.

Algorithm for TOH problem:

Let’s consider move ‘n’ disks from source peg (A) to destination peg (C), using intermediate peg (B) as auxiliary.

1. Assign three pegs A, B & C

2. If n==1

Move the single disk from A to C and stop.

3. If n>1

a) Move the top (n-1) disks from A to B.

b) Move the remaining disks from A to C

c) Move the (n-1) disks from B to C

4. Terminate

Example for 3 disks: 7 moves

Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which, we can traverse every vertex of the graph. 

The Kruskal's algorithm is given as follows:

1. List all the edges of G with non-decreasing order of their weights.

2. Select an edge of minimum weight. This will be the first edge of T.

3. At each stage, select an edge of minimum weights from all remaining edges of G if it doesn’t form a cycle with previously selected edges in T. Then add the edge to T.

4. Repeat step 3 until n-1 edges have been selected.

Example:

Edges of given graph with non-decreasing order of their weights:

Pick edge (1, 6): No cycle is formed, include it. 

Pick edge (4,3): No cycle is formed, include it. 

Pick edge (2,7): No cycle is formed, include it.