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