Inorder successor for BST

Inorder traversal:

left
root
right

Algorithm:

1. Perform inorder traversal.
2. Locate the required node (q) first.
3. if 'q' found, print the next node and exit

#define TRUE 1
#define FALSE 0

void isuccessor(node *p, node *q) {
 
 // used to identify whether the given node is found
 static int is_node_found = FALSE;
 
 // if either of this are null, return
 if( !p || !q) 
  return;
 
 // left sub-tree
 isuccessor(p->left, q);
 
 // root, i.e. logic foreach node is done here
 // already q found, print this node and quit
 if( is_node_found ) {
  printf("%d", node->info);
  exit(0);
 }
 
 // we have found q
 if( q->info == p->info ) {
  is_node_found = TRUE; 
       
 } 
 
 // right sub-tree
 isuccessor(p->right, q);
}

Split linked list on alternate nodes

Pseudocode:

The code is self explanatory.

node* split( node *list) {


 node *p, node *q, node *new;
 
 // we need atleast 2 nodes to split
 if( !list || !list->next )
  return NULL;
  
 // p points to second node
 // q points to first node 
 // q trails p
  
 q = list;
 p = list->next;


 while( p && q ) {


  q->next = p->next;
  
  if( q->next )
   p->next = q->next->next;
  else {
   p->next = NULL;
   break;
  }
  
  // increment pointers
  p = p->next;
  q = q->next;
 }


 return new;
}

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