Code for Run Length Encoding

Algorithm:

step 1: input string s, char *c
step 2: c = s;
step 3: foreach character *c, in the string s,
step 4: compare subsequent characters *p, if equal, inc counter till *p != *c
step 5: append c and count to enc_string
step 6: reset count to 1
step 7: make c = p;
step 8: end for

Program:

char* encode(char *s) {
 char *c, *p; char enc[100]; int count = 1, i = 0;
 if( s == NULL ) 
  return NULL;
 c = s;


 while( *c ) {
  if( !(*(c+1) ) { //end of string, append c and count
   enc[i++] = c;
   enc[i++] = count;
   count = 1;
   break;
  }
  p = c+1;
  
  while( *p == *c ) {
   p++;
   count++;
  }
  enc[i++] = c;
  enc[i++] = count;
  count = 1;
  c = p;
 }
 return enc;
}

BST post-order Traversal (Recursive Code and Complexity)

Pre-condition:

typedef struct intnode {
 int info;
 node *left, *right; 
}node;

Algorithm:
step 1: if pointer is null, return;
step 2: visit left-sub tree, repeat step 1
step 3: visit right-sub-tree, repeat step 1
step 4: visit root
step 5: stop

Code:

void postorder(node *p){
 // if pointer is null, return
 if( p == NULL )
  return; 
  
 // visit left
 postorder( p->left );
 
 // visit right
 postorder( p->right );
 
 // visit root
 printf("%d ", p->info );
 
 return;
}

Complexity:
O(n), because each node has to be visited atleast once and increases linearly for increasing 'n'.

BST pre-order Traversal (Recursive Code and Complexity)

Pre-condition:

typedef struct intnode {
 int info;
 node *left, *right;
}node;

Algorithm:
step 1: if pointer is null, return;
step 2: visit root
step 3: visit left sub-tree, repeat step 1
step 4: visit right sub-tree, repeat step 1
step 5: stop

Code:

void preorder(node *p){
 // if pointer null, return
 if( p == NULL )
  return; 
  
 // visit root
 printf("%d ", p->info);
 
 // visit left-sub-tree
 preorder( p->left );
 
 // visit right-sub-tree
 preorder( p->right );
}

Complexity:
O(n), because each node has to be visited atleast once and increases linearly for increasing 'n'.

BST in-order Traversal (Recursive Code and Complexity)

Pre-condition:

typedef struct intnode {
 int info;
 node *left, *right; 
}node;

Algorithm:
step 1: if pointer is null, return;
step 2: visit left sub-tree
step 3: visit root
step 4: visit right sub-tree
step 5: stop

Code:

void inorder(node *p) {
 // if p is null return
 if( p == null )
  return;
 // left sub-tree
 inorder(p->left);
 // root
 printf("%d", p->info);
 //right sub-tree
 inorder(p->right);
}

Complexity:
O(n), because each node has to be visited atleast once and increases linearly for increasing 'n'.

Print first unique character in a stirng

Precondition:

Assume only ascii characters.

Algorithm:

step 1: Declare c[128] = {0}
step 2: for each element in string s,
stpe 3: increment *(c+(int)s[i]])
step 4: end for
step 5: for each element in c
step 6: if count is 1, break and (char)i is the unique char
step 7: end for

step 8: if i == 128, no unique char

Code:

char find_unique(char *s){
 
 int a[128] = {0};
 char c;


 // count the number of occurances of each element in the array
 while( c = *s++ ){
  a[c]++;
 }
 
 // check for the char with exactly one occurance
 for( i=0;i<128;i++)
  if( a[i] == 1)
   break;  
 
 // means no element is unique, return null
 if( i == 128 )
  return '\0';
 
 return (char)i;
 
}

Find nth smallest element in binary search tree

#A binary search tree was given. Tell the 4th smallest value in it.

// traverse tree in in order, this will give the output in ascending order, take the fourth element or a[3];

int min = -1; // global variable

void traverse(NODE *p) {
    
    static int index = -1;
    
    // for any node, if index is 3, we have found the element do nothing
    if( p == null || index == 3 )
        return;
    
    // else traverse left tree first, i.e. in order traversal
    traverse( p->left );

    // element found somewhere in left sub-tree
    if( index == 3 ) 
        return; 
    
    // element not found yet, use current node info
    index++; min = p->info;

    // traverse right sub-tree
    traverse( p->right );
}

Note: not tested, suggest better methods if possible 

Complexity: O(n)

Number of noded traversed depends upon the depty and the distribution of the binary tree.

Reverse linked list

// reverse linked list with recursion

node* reverse(node *prev, node *cur){
    
    // occurs only for last_node->next
    if( cur == null )
        return prev;
    
    node *temp = cur->next;
    cur->next = prev;
    
    return reverse(cur, temp);
}

int main(){
    node *p = /* linked list */;
    p = reverse(NULL, p);
    return 0;
}

// reverse linked list without recursion

int main() {

NODE *head = /* given list */, *cur = head, *prev = NULL, *temp = NULL;

while( cur -> next ) {
    temp = cur -> next;
    cur -> next = prev;
    prev = cur;
    cur = temp;
}
head = cur; // end of iteration, cur will point to last

return 0;
}