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

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

Find loop in linked list

Algorithm:

1. Have 2 pointers *fast and *slow.
2. Increment fast twice as fast as slow. 
3. If there is a loop, sooner or later fast will catch slow. 

#define TRUE 1
#define FALSE 0

int main() {
    NODE *head = /* given list*/, *fast = head, *slow = head;
    int is_looped = FALSE;

    while( fast && (fast = fast->next) && (fast = fast->next) ) {
        
        if( slow == fast ) {
            is_looped = TRUE;
            break;
        }
        slow = slow->next;        
    }
    // is_looped is true if there is a loop           
}

Delete linked list

int main() {
    NODE *p, *temp;
    while(p) {
        temp = p;
        p = p->next;
        free(temp);
    }
    return 0;
}

Insert node in the middle of linked list

void insertMiddleNode(NODE *head, NODE *new_node) {

    if( head == NULL || new_node == NULL )
        return; 
        
    NODE *fast, *slow;
    fast = slow = head; 
    
    // move fast 2 positions

    while (fast && (fast = fast->next) && (fast = fast->next)) {
        //move slow one position
        slow = slow->next;
    }

    // now slow is middle node
    new_node->next = slow->next;
    slow->next = new_node;
}

Find the character that repeats most in a string

Solution 1:

// declare an alphabet array
int counter[26] = {0};
char *string = "inputstringofcharacters"; 
char ch; int i=0;

// foreach alphabet in input string, increment counter by 1
while( ch = *(string + i++) ) {
    *(counter + (int)ch)++;    
}

// find the max of array.
int max_count = 0;
char max_element;

for( i=0; i<26 data-blogger-escaped-counter="" data-blogger-escaped-i="" data-blogger-escaped-if=""> max_count) {
        max_count = counter[i];
        max_element = (char)i;
    }
}

Complexity: 

Traverse complete array once, O(n) 

Traverse the count array once, O(26) 

Total complexity O(26*n) = O(n) 

Solution 2:

typedef struct node {
    char info;
    node *left, *right;
}NODE;

// traverse input and construct binary search tree O(n)

// find the max element in the binary search tree O(log n)

Complexity: O(n log n)

Merge 2 sorted linked list

In this algorithm, we pick nodes from list q and insert in the right position in the list p.

step 1: foreach node in p (t always follows p, one step behind)
step 2: compare p->info with q->info
step 3: if q<=p, stuff q between p and t, q = q->next, t=q
step 4: else take next node from p and repeat step 2

// takes two linked list and returns pointer to new list
node* merge_sorted_linked_list(node *p, node *q) {

    node *list = p, *temp, *t = null; /* t always trails p */
    
    if( p == NULL )
        return q;
    
    if ( q == NULL )
        return p;
    
    // store the head of resulting list
    if( q->info <= p->info ) 
        list = q; 
        
    while( p && q ) {    
            
        if( q->info <= p->info ) {
            
            // q->next will be changed now
            temp = q->next;
            
            // stuff q between t and p
            if( t != NULL )    t->next = q; 
            q->next = p;
            
            // advance t, now q is a part of the first list
            t = q;    
            
            // q++
            q = temp;            
        } else {
            // advance p, consequently t also
            t = p;
            p = p->next; 
        }    
    }

    if( p == NULL )
        t->next = q;
        
    return list; 
}

Check equality for linked list

Input:

p = 1 > 2 > 3 > 4 > NULL;
q = 1 > 2 > 3 > 4 > NULL;

Output: TRUE

#define TRUE 1
#define FALSE 0

int check(NODE *p, NODE *q) {

    if( p == NULL && q == NULL)
        return TRUE;
        
    while( p != NULL ) {
        
        if( q == NULL )
            return FALSE;
            
        if( p->info != q->info )
            return FALSE;            
        
        p = p->next;
        q = q->next;
    }
}

Reverse linked list in groups of given size

Sample #1:
k = 3
Input: 1->2->3->4->5->6->7->8->NULL
Output: 3->2->1->6->5->4->8->7->NULL.

Sample #2:
k = 5
Input: 1->2->3->4->5->6->7->80->NULL
Output: 5->4->3->2->1->8->7->6->NULL

// takes head pointer, reverse the list and return new head pointer
NODE* reverse(NODE *head, int k) {
    
    NODE *cur, *prev = NULL, *temp = NULL;    int i;    

    if( head == NULL ) 
        return NULL;
        
    cur = head;
        
    // end of for loop, cur will become the last node
    for( i=0; inext == NULL ) {
            cur->next = prev;
            return cur;
        }
            
        temp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = temp;
    }
 
    head->next = reverse( cur, k );
    return prev;    
}

int main() {

    NODE *head = /* linked list */, *tail;    
    head = reverse( head, 3 );
}

Reverse a Linked List using recursion

Input: 1->2->3->4->5->6->7->8->NULL
Output: 8->7->6->5->4->3->2->1->NULL

// take head pointer and return new head pointer
void reverse(NODE *head) {

    NODE *cur, *prev = NULL, *temp = NULL;
    
    if( head == NULL )
        return null; 
        
    cur = head; 
    
    while( cur ){        
    
        if( cur->next == null ) {
            cur->next = prev;
            return cur;
        }
            
        temp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = temp;
    }    
} 

int main(){
  NODE *head = /* linked list */;
  NODE *reverse_list = reverse(head);
}