Populate next higher in a singly linked list

Problem

/*

   Algo:  This is similar to insertion sort algorithm

*/

#include <stdio.h>
#include <stdlib.h>

typedef struct node {

    int data;
    struct node *next;
    struct node *next_higher;

}Node;


typedef Node *List;


List populateNextHigher(List l) {

    if(!l) return NULL;

    Node *start = l; //starting of the sorted list
    l = l->next;

    while(l){ //iterate through the list

        if(l->data < start->data){  

            l->next_higher = start;
            start = l;

        } else {

            Node *p = start;

            while(p->next_higher && l->data >= p->next_higher->data) //find the position of l 
                p = p->next_higher;

            l->next_higher = p->next_higher; //insert l
            p->next_higher = l;

        }
        l = l->next;
    }

    return start;
}


//Utilities

Node *makeNode(int n) {
    Node *node = calloc(1, sizeof(Node));

    node->data = n;
}

List array2List(int a[], int n){

    List l = NULL;

    if(n > 0) {
        Node *end = l = makeNode(a[0]);
        int i;

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

            end->next = makeNode(a[i]);
            end = end->next;
        }
    }

    return l;

}


void printList(List l) {

    while(l){
        printf("%d ", l->data);
        l = l->next_higher;
    }

    printf("\n");
}

int main(){

    int a[] = {90, 80, 60, 70, 50, 40,100};

    List l = array2List(a, sizeof(a)/sizeof(int));

    List h = populateNextHigher(l);
    printList(h);

    return 0;
}

To find minimum distance of two sorted lists where distance is the absolute difference of pair of elements

Problem

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

int minDist(int a[], int m, int b[], int n){

    int i = 0,
        j = 0, 
        min = INT_MAX,
        cur;

    while(i < m && j < n) {

        cur = abs(a[i] - b[j]);

        min  = min < cur ? min : cur;

        if(a[i] < b[j])
            i++;
        else
            j++;
    }

    return min;
}

int main() {

    int a[] = {2, 3, 5, 11, 18, 19, 20};
    int b[]= {15, 24, 27, 29};


    printf("%d\n", minDist(a, sizeof(a)/sizeof(int), b, sizeof(b)/sizeof(int)));

    return 0;
}

reorder linked list as even elements followed by odd elements

#include <stdio.h>
#include <stdlib.h>


typedef struct node {
    int data;
    struct node *next;
}Node;

typedef Node * List;


/*
arranges the list as event elements followed by odd elements in single pass
*/
void evenOddList(List l){

    if(!l) return;

    Node *even = NULL, 
         *odd  = NULL,
         *start = NULL;

    if(l->data & 1)
        odd = l;
    else
        even = l;

    l = l->next;

    while(l) {

        if(l->data & 1) {//odd 

            if(odd)
                odd->next = l;
            else
                 start = l;

            odd = l;

        }else { //even

            if(even)
                 even->next = l;
            else
                 start = l; 

            even = l;
        }

        l = l->next;
    }

    if(start) {
        if(start->data & 1) {//odd

            even->next = start;
            odd->next = NULL;

        }else {//even

            odd->next = start;
            even->next = NULL;
        }
    }

}


List append(List l, int e) {

    static Node *end = NULL;

    Node *n = calloc(sizeof(Node), 1);

    n->data = e;

    if(end) {
        end->next = n;
    }else {
        l = n;
    }

    end = n;    

    return l;

}


void printList(List l) {

    Node *n = l;

    while(l) {

        printf("%d ", l->data);

        l = l->next;
    }

    printf("\n");
}


int main() {

    int a[]= {13, 11, 28, 45, 58, 69, 34, 23, 86};


    List l = NULL;

    int i;

    for(i = 0; i < sizeof(a)/sizeof(int); ++i) {
        
         l = append(l, a[i]);

    }


    printList(l);

    evenOddList(l);

    printList(l);
    return 0;
}

Max breadth of a binary tree

#include <stdio.h>
#include <stdlib.h>
#include <list>

typedef struct TreeNode {
    struct TreeNode *left, *right;
    int data;

}TreeNode;


typedef TreeNode * Tree;

/*
*Function which returns maximum width of a binary tree without recursion

We are using level order traversal
*/

int Width(Tree t) {

    int width = -1;

    if(t != NULL) {

        std::list<Tree> q; //Queue to store tree nodes

        q.push_back(t);
        q.push_back(NULL); //null is the delimeter to show end  of the level

        int cur = 0;

        while(!q.empty()) {

            TreeNode *node = q.front();
            q.pop_front();

            if(node == NULL) {//delimeter encountered, compare width with cur width and push NULL if q not empty 

                if(width < cur)
                    width = cur;

                cur = 0;

                if(!q.empty())
                    q.push_back(NULL);

            }
            else {

                cur++;

                if(node->left)
                    q.push_back(node->left);

                if(node->right)
                    q.push_back(node->right);
            }
        }

    }

    return width;
}


/*Utilities*/

inline  TreeNode * makeTreeNode(int data) {

    TreeNode *n = (TreeNode *)calloc(sizeof(TreeNode), 1);
    n->data = data;

    return n;
}


int main() {

    /*level 0*/
    Tree t = makeTreeNode(10);

    /*level 1*/
    t->left = makeTreeNode(20);
    t->right = makeTreeNode(30);


    /*level 2*/
    t->left->left = makeTreeNode(40);
    t->left->right = makeTreeNode(70);
    t->right->left = makeTreeNode(50);
    t->right->right = makeTreeNode(60);

    /*level 3*/
    t->left->left->left = makeTreeNode(70);
    t->left->left->right = makeTreeNode(70);
    t->left->right->left = makeTreeNode(70);
    t->left->right->right = makeTreeNode(70);
    t->right->left->left = makeTreeNode(60);
    t->right->left->right = makeTreeNode(160);
    t->right->right->left = makeTreeNode(60);
    t->right->right->right = makeTreeNode(160);

    /*level 4*/
    t->left->left->left->left = makeTreeNode(70);

    printf("%d\n", Width(t));

    return 0;
}

finding minimum number of platforms required if arrival and departure time of trains given in sorted order of arrival time

#include <stdio.h>

typedef struct {

    int a, d;
}Train;



int minPlatform(Train a[], int n) {

    int platforms[n];

    int i, j;
    int num = 1;

    platforms[0] = a[i].d; //time when plaform 0 will be free

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

        for(j = 0; j < num; ++j) {

            if(platforms[j] < a[i].a) { //arrival time  is after freeing the platform

                platforms[j] = a[i].d; //assign platform j to train i

                break;
            }
        }

        if(j == num) { //all platforms busy
            platforms[num] = a[i].d;  //allocate one more platform
            num++;
        }

    }


    return num;
}


int main() {


    Train a[] = {{1, 10}, {9, 13}, {10, 15}, {17,20}, {20, 22}, {24, 25}};


    printf("%d\n", minPlatform(a, sizeof(a)/sizeof(Train)));

    return 0;
}

Create a singly linked list of Leaf nodes from a binary tree

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode
{
    struct TreeNode *left, *right, *next;
    int data;

}TreeNode;

typedef TreeNode * Tree;

void LeafLinked(Tree t, TreeNode **prevLeaf, TreeNode **head)
{
    if(t) {

        if(t->left == NULL && t->right == NULL) { //leaf

            if(*head == NULL)
                *head = t;

            else if(*prevLeaf)
                (*prevLeaf)->next = t;

            *prevLeaf = t;
        }
        else { //at least one child
            LeafLinked(t->left, prevLeaf, head);
            LeafLinked(t->right, prevLeaf, head);
        }
    }
}


/*Utilities*/

inline  TreeNode * makeTreeNode(int data)
{
    TreeNode *n = calloc(sizeof(TreeNode), 1);
    n->data = data;

    return n;
}

inline void printList(Tree t)
{
    while(t)
    {
        printf("%d ", t->data);
        t = t->next;
    }
    printf("\n");
}

int main()
{
    /*level 0*/
    Tree t = makeTreeNode(10);

    /*level 1*/
    t->left = makeTreeNode(20);
    t->right = makeTreeNode(30);


    /*level 2*/
    t->left->left = makeTreeNode(40);
    t->left->right = makeTreeNode(70);
    t->right->left = makeTreeNode(50);
    t->right->right = makeTreeNode(60);

    /*level 3*/
    t->left->left->left = makeTreeNode(70);
    t->right->right->left = makeTreeNode(60);
    t->right->right->right = makeTreeNode(160);

    /*Empty List head*/
    TreeNode *head = NULL, *prevLeaf = NULL;

    /*Convert tree to list*/
    LeafLinked(t, &prevLeaf, &head);

    /*print list*/
    printList(head);


    return 0;
}

Python Version:

class BinaryTree:

    def __init__(self, e):
        self.left = self.right = self.next = None
        self.data = e


def LinkLeaves(t):

    if t:
        if t.left  or t.right:

            for x in LinkLeaves(t.left):
                yield x

            for x in LinkLeaves(t.right):
                yield x
        else:
            yield t

def printList(t):

    while  t:
        print t.data,
        t = t.next
    print

def  main():

    t = BinaryTree(10);

    t.left = BinaryTree(20)
    t.right = BinaryTree(30)

    t.left.left = BinaryTree(40)
    t.left.right = BinaryTree(70)
    t.right.left = BinaryTree(50)
    t.right.right = BinaryTree(60)

    t.left.left.left = BinaryTree(70)
    t.right.right.left = BinaryTree(60)
    t.right.right.right = BinaryTree(160)

    head = None
    prevLeaf = None

    for x in LinkLeaves(t):
        if head is None:
            head = x
        else:
            prevLeaf.next = x

        prevLeaf = x

    printList(head)


if __name__ == '__main__':
    main()

find two elements in a binary search tree whose sum is given k

class BinarySearchTree:

    def __init__(self, e = None):
        self.left = self.right = None
        self.data = e

    def insert(self, e):

        if self.data is None:
            self.data = e
        else:
            if self.data >= e:
                if self.left is None:
                    self.left = BinarySearchTree(e)
                else:
                    self.left.insert(e)
            else:
                if self.right is None:
                    self.right = BinarySearchTree(e)
                else:
                    self.right.insert(e)

    def nextMin(self):

        if self.left:
            for x in  self.left.nextMin():
                yield x

        yield self.data

        if self.right:
            for x in self.right.nextMin():
                yield x

    def nextMax(self):

        if self.right:
            for x in self.right.nextMax():
                yield x

        yield self.data

        if self.left:
            for x in  self.left.nextMax():
                yield x

    def findxy(self, k):

        if self.data:

            mn = self.nextMin()
            mx = self.nextMax()

            m = mn.next()
            n = mx.next()

            while True:

                sm = m + n

                try:
                    if sm == k:
                        return m,n
                    elif sm < k :
                        m  = mn.next()
                    else:
                        n = mx.next()
                except:
                    return None


def main():
    l = [50, 80, 30, 20, 40,  70, 60]

    t = BinarySearchTree()

    for i in l:
        t.insert(i)

    print t.findxy(120)


if __name__ == '__main__':
    main()

reverse an array of integers using recursion

#include <stdio.h>


void reverse(int a[], int start, int end) {

    if(start < end) {
        int tmp = a[start];
        a[start] = a[end];
        a[end] = tmp;

        reverse(a, start + 1, end - 1);

    }

}


int main() {

    int a[] = {100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 1};

    reverse(a, 0, 10);


    int i;

    for(i = 0; i < 11; ++i){
        printf("%d ", a[i]);
    }

    printf("\n");
    return 0;
}

Height of a binary tree without recursion

#include <stdio.h>
#include <stdlib.h>
#include <list>

typedef struct TreeNode {
    struct TreeNode *left, *right;
    int data;

}TreeNode;


typedef TreeNode * Tree;

/*
*Function which returns height of a binary tree without recursion

We are using level order traversal
*/

int Height(Tree t) {

    int height = -1;

    if(t != NULL) {

        std::list<Tree> q; //Queue to store tree nodes

        q.push_back(t);
        q.push_back(NULL); //null is the delimeter to show end  of the level

        while(!q.empty()) {

            TreeNode *node = q.front();
            q.pop_front();

            if(node == NULL) {//delimeter encountered, increase height and push NULL if q not empty 

                height++;

                if(!q.empty())
                    q.push_back(NULL);

            }
            else {

                if(node->left)
                    q.push_back(node->left);

                if(node->right)
                    q.push_back(node->right);
            }

        }

    }

    return height;
}


/*Utilities*/

inline  TreeNode * makeTreeNode(int data) {

    TreeNode *n = (TreeNode *)calloc(sizeof(TreeNode), 1);
    n->data = data;

    return n;
}


int main() {

    /*level 0*/
    Tree t = makeTreeNode(10);

    /*level 1*/
    t->left = makeTreeNode(20);
    t->right = makeTreeNode(30);


    /*level 2*/
    t->left->left = makeTreeNode(40);
    t->left->right = makeTreeNode(70);
    t->right->left = makeTreeNode(50);
    t->right->right = makeTreeNode(60);

    /*level 3*/
    t->left->left->left = makeTreeNode(70);
    t->right->right->left = makeTreeNode(60);
    t->right->right->right = makeTreeNode(160);

    /*level 4*/
    t->left->left->left->left = makeTreeNode(70);

    printf("%d\n", Height(t));

    return 0;
}