WAP for SKIP List...Google Asked It

/* skip list */

#include
#include

/* implementation dependent declarations */
typedef enum {
STATUS_OK,
STATUS_MEM_EXHAUSTED,
STATUS_DUPLICATE_KEY,
STATUS_KEY_NOT_FOUND
} statusEnum;

typedef int keyType; /* type of key */

/* user data stored in tree */
typedef struct {
int stuff; /* optional related data */
} recType;

#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/* levels range from (0 .. MAXLEVEL) */
#define MAXLEVEL 15

typedef struct nodeTag {
keyType key; /* key used for searching */
recType rec; /* user data */
struct nodeTag *forward[1]; /* skip list forward pointer */
} nodeType;

/* implementation independent declarations */
typedef struct {
nodeType *hdr; /* list Header */
int listLevel; /* current level of list */
} SkipList;

SkipList list; /* skip list information */

#define NIL list.hdr

statusEnum insert(keyType key, recType *rec) {
int i, newLevel;
nodeType *update[MAXLEVEL+1];
nodeType *x;

/***********************************************
* allocate node for data and insert in list *
***********************************************/

/* find where key belongs */
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->key, key))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x != NIL && compEQ(x->key, key))
return STATUS_DUPLICATE_KEY;

/* determine level */
for (
newLevel = 0;
rand() < RAND_MAX/2 && newLevel < MAXLEVEL;
newLevel++);

if (newLevel > list.listLevel) {
for (i = list.listLevel + 1; i <= newLevel; i++)
update[i] = NIL;
list.listLevel = newLevel;
}

/* make new node */
if ((x = malloc(sizeof(nodeType) + newLevel*sizeof(nodeType *))) == 0)
return STATUS_MEM_EXHAUSTED;
x->key = key;
x->rec = *rec;

/* update forward links */
for (i = 0; i <= newLevel; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
return STATUS_OK;
}

statusEnum delete(keyType key) {
int i;
nodeType *update[MAXLEVEL+1], *x;

/*******************************************
* delete node containing data from list *
*******************************************/

/* find where data belongs */
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->key, key))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x == NIL || !compEQ(x->key, key)) return STATUS_KEY_NOT_FOUND;

/* adjust forward pointers */
for (i = 0; i <= list.listLevel; i++) {
if (update[i]->forward[i] != x) break;
update[i]->forward[i] = x->forward[i];
}

free (x);

/* adjust header level */
while ((list.listLevel > 0)
&& (list.hdr->forward[list.listLevel] == NIL))
list.listLevel--;

return STATUS_OK;
}

statusEnum find(keyType key, recType *rec) {
int i;
nodeType *x = list.hdr;

/*******************************
* find node containing data *
*******************************/

for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->key, key))
x = x->forward[i];
}
x = x->forward[0];
if (x != NIL && compEQ(x->key, key)) {
*rec = x->rec;
return STATUS_OK;
}
return STATUS_KEY_NOT_FOUND;
}

void initList() {
int i;

/**************************
* initialize skip list *
**************************/

if ((list.hdr = malloc(
sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *))) == 0) {
printf ("insufficient memory (initList)\n");
exit(1);
}
for (i = 0; i <= MAXLEVEL; i++)
list.hdr->forward[i] = NIL;
list.listLevel = 0;
}

int main(int argc, char **argv) {
int i, maxnum, random;
recType *rec;
keyType *key;
statusEnum status;


/* command-line:
*
* skl maxnum [random]
*
* skl 2000
* process 2000 sequential records
* skl 4000 r
* process 4000 random records
*
*/

maxnum = atoi(argv[1]);
random = argc > 2;

initList();

if ((rec = malloc(maxnum * sizeof(recType))) == 0) {
fprintf (stderr, "insufficient memory (rec)\n");
exit(1);
}
if ((key = malloc(maxnum * sizeof(keyType))) == 0) {
fprintf (stderr, "insufficient memory (key)\n");
exit(1);
}

if (random) {
/* fill "a" with unique random numbers */
for (i = 0; i < maxnum; i++) key[i] = rand();
printf ("ran, %d items\n", maxnum);
} else {
for (i = 0; i < maxnum; i++) key[i] = i;
printf ("seq, %d items\n", maxnum);
}

for (i = 0; i < maxnum; i++) {
status = insert(key[i], &rec[i]);
if (status) printf("pt1: error = %d\n", status);
}

for (i = maxnum-1; i >= 0; i--) {
status = find(key[i], &rec[i]);
if (status) printf("pt2: error = %d\n", status);
}

for (i = maxnum-1; i >= 0; i--) {
status = delete(key[i]);
if (status) printf("pt3: error = %d\n", status);
}
return 0;
}

WAP for RED Black Tree(height Balanced Binary Tree)

// red-black tree

#include
#include
#include
#include

//////////////////////
// supplied by user //
//////////////////////

typedef int KeyType; // type of key

typedef struct { // value related to key
int stuff;
} ValType;

// how to compare keys
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/////////////////////////////////////
// implementation independent code //
/////////////////////////////////////

typedef enum {
RBT_STATUS_OK,
RBT_STATUS_MEM_EXHAUSTED,
RBT_STATUS_DUPLICATE_KEY,
RBT_STATUS_KEY_NOT_FOUND
} RbtStatus;

typedef enum { BLACK, RED } nodeColor;

typedef struct NodeTag {
struct NodeTag *left; // left child
struct NodeTag *right; // right child
struct NodeTag *parent; // parent
nodeColor color; // node color (BLACK, RED)
KeyType key; // key used for searching
ValType val; // data related to key
} NodeType;

#define SENTINEL &sentinel // all leafs are sentinels
static NodeType sentinel = { SENTINEL, SENTINEL, 0, BLACK, 0};

static NodeType *root = SENTINEL; // root of red-black tree

static void rotateLeft(NodeType *x) {

// rotate node x to left

NodeType *y = x->right;

// establish x->right link
x->right = y->left;
if (y->left != SENTINEL) y->left->parent = x;

// establish y->parent link
if (y != SENTINEL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->left)
x->parent->left = y;
else
x->parent->right = y;
} else {
root = y;
}

// link x and y
y->left = x;
if (x != SENTINEL) x->parent = y;
}

static void rotateRight(NodeType *x) {

// rotate node x to right

NodeType *y = x->left;

// establish x->left link
x->left = y->right;
if (y->right != SENTINEL) y->right->parent = x;

// establish y->parent link
if (y != SENTINEL) y->parent = x->parent;
if (x->parent) {
if (x == x->parent->right)
x->parent->right = y;
else
x->parent->left = y;
} else {
root = y;
}

// link x and y
y->right = x;
if (x != SENTINEL) x->parent = y;
}

static void insertFixup(NodeType *x) {

// maintain red-black tree balance
// after inserting node x

// check red-black properties
while (x != root && x->parent->color == RED) {
// we have a violation
if (x->parent == x->parent->parent->left) {
NodeType *y = x->parent->parent->right;
if (y->color == RED) {

// uncle is RED
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {

// uncle is BLACK
if (x == x->parent->right) {
// make x a left child
x = x->parent;
rotateLeft(x);
}

// recolor and rotate
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateRight(x->parent->parent);
}
} else {

// mirror image of above code
NodeType *y = x->parent->parent->left;
if (y->color == RED) {

// uncle is RED
x->parent->color = BLACK;
y->color = BLACK;
x->parent->parent->color = RED;
x = x->parent->parent;
} else {

// uncle is BLACK
if (x == x->parent->left) {
x = x->parent;
rotateRight(x);
}
x->parent->color = BLACK;
x->parent->parent->color = RED;
rotateLeft(x->parent->parent);
}
}
}
root->color = BLACK;
}

// insert new node (no duplicates allowed)
RbtStatus rbtInsert(KeyType key, ValType val) {
NodeType *current, *parent, *x;

// allocate node for data and insert in tree

// find future parent
current = root;
parent = 0;
while (current != SENTINEL) {
if (compEQ(key, current->key))
return RBT_STATUS_DUPLICATE_KEY;
parent = current;
current = compLT(key, current->key) ?
current->left : current->right;
}

// setup new node
if ((x = malloc (sizeof(*x))) == 0)
return RBT_STATUS_MEM_EXHAUSTED;
x->parent = parent;
x->left = SENTINEL;
x->right = SENTINEL;
x->color = RED;
x->key = key;
x->val = val;

// insert node in tree
if(parent) {
if(compLT(key, parent->key))
parent->left = x;
else
parent->right = x;
} else {
root = x;
}

insertFixup(x);

return RBT_STATUS_OK;
}

static void deleteFixup(NodeType *x) {

// maintain red-black tree balance
// after deleting node x

while (x != root && x->color == BLACK) {
if (x == x->parent->left) {
NodeType *w = x->parent->right;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateLeft (x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
rotateRight (w);
w = x->parent->right;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->right->color = BLACK;
rotateLeft (x->parent);
x = root;
}
} else {
NodeType *w = x->parent->left;
if (w->color == RED) {
w->color = BLACK;
x->parent->color = RED;
rotateRight (x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK) {
w->color = RED;
x = x->parent;
} else {
if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
rotateLeft (w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
rotateRight (x->parent);
x = root;
}
}
}
x->color = BLACK;
}

// delete node
RbtStatus rbtErase(NodeType * z) {
NodeType *x, *y;

if (z->left == SENTINEL || z->right == SENTINEL) {
// y has a SENTINEL node as a child
y = z;
} else {
// find tree successor with a SENTINEL node as a child
y = z->right;
while (y->left != SENTINEL) y = y->left;
}

// x is y's only child
if (y->left != SENTINEL)
x = y->left;
else
x = y->right;

// remove y from the parent chain
x->parent = y->parent;
if (y->parent)
if (y == y->parent->left)
y->parent->left = x;
else
y->parent->right = x;
else
root = x;

if (y != z) {
z->key = y->key;
z->val = y->val;
}


if (y->color == BLACK)
deleteFixup (x);

free (y);

return RBT_STATUS_OK;
}

// find key
NodeType *rbtFind(KeyType key) {
NodeType *current;
current = root;
while(current != SENTINEL) {
if(compEQ(key, current->key)) {
return current;
} else {
current = compLT (key, current->key) ?
current->left : current->right;
}
}
return NULL;
}

// in-order walk of tree
void rbtInorder(NodeType *p, void (callback)(NodeType *)) {
if (p == SENTINEL) return;
rbtInorder(p->left, callback);
callback(p);
rbtInorder(p->right, callback);
}

// delete nodes depth-first
void rbtDelete(NodeType *p) {
if (p == SENTINEL) return;
rbtDelete(p->left);
rbtDelete(p->right);
free(p);
}

void displayNode(NodeType *p) {
printf("%d %d\n", p->key, p->val.stuff);
}

int main(int argc, char **argv) {
int maxnum, ct;
KeyType key;
RbtStatus status;

// command-line:
//
// rbt 2000
// process 2000 records

NodeType *p;

maxnum = atoi(argv[1]);

printf("maxnum = %d\n", maxnum);
for (ct = maxnum; ct; ct--) {
key = rand() % 90 + 1;
if ((p = rbtFind(key)) != NULL) {
if (p->val.stuff != 10*key) printf("fail val\n");
status = rbtErase(p);
if (status) printf("fail: status = %d\n", status);
} else {
ValType val;
val.stuff = 10*key;
status = rbtInsert(key, val);
if (status) printf("fail: status = %d\n", status);
}
}

// output nodes in order
rbtInorder(root, displayNode);

rbtDelete(root);

return 0;
}

WAP For Hashing ..Hash Table Implementataion

/* hash table */

#include
#include

/* implementation dependent declarations */
typedef int keyType; /* type of key */

/* user data stored in hash table */
typedef struct {
int stuff; /* optional related data */
} recType;

typedef int hashIndexType; /* index into hash table */

#define compEQ(a,b) (a == b)


/* implementation independent declarations */
typedef enum {
STATUS_OK,
STATUS_MEM_EXHAUSTED,
STATUS_KEY_NOT_FOUND
} statusEnum;

typedef struct nodeTag {
struct nodeTag *next; /* next node */
keyType key; /* key */
recType rec; /* user data */
} nodeType;

nodeType **hashTable;
int hashTableSize;

hashIndexType hash(keyType key) {

/***********************************
* hash function applied to data *
***********************************/

return (key % hashTableSize);
}

statusEnum insert(keyType key, recType *rec) {
nodeType *p, *p0;
hashIndexType bucket;

/************************************************
* allocate node for data and insert in table *
************************************************/

/* insert node at beginning of list */
bucket = hash(key);
if ((p = malloc(sizeof(nodeType))) == 0)
return STATUS_MEM_EXHAUSTED;
p0 = hashTable[bucket];
hashTable[bucket] = p;
p->next = p0;
p->key = key;
p->rec = *rec;
return STATUS_OK;
}

statusEnum delete(keyType key) {
nodeType *p0, *p;
hashIndexType bucket;

/********************************************
* delete node containing data from table *
********************************************/

/* find node */
p0 = 0;
bucket = hash(key);
p = hashTable[bucket];
while (p && !compEQ(p->key, key)) {
p0 = p;
p = p->next;
}
if (!p) return STATUS_KEY_NOT_FOUND;

/* p designates node to delete, remove it from list */
if (p0)
/* not first node, p0 points to previous node */
p0->next = p->next;
else
/* first node on chain */
hashTable[bucket] = p->next;

free (p);
return STATUS_OK;
}

statusEnum find(keyType key, recType *rec) {
nodeType *p;

/*******************************
* find node containing data *
*******************************/

p = hashTable[hash(key)];
while (p && !compEQ(p->key, key))
p = p->next;
if (!p) return STATUS_KEY_NOT_FOUND;
*rec = p->rec;
return STATUS_OK;
}

int main(int argc, char **argv) {
int i, maxnum, random;
recType *rec;
keyType *key;
statusEnum err;

/* command-line:
*
* has maxnum hashTableSize [random]
*
* has 2000 100
* processes 2000 records, tablesize=100, sequential numbers
* has 4000 200 r
* processes 4000 records, tablesize=200, random numbers
*
*/
maxnum = atoi(argv[1]);
hashTableSize = atoi(argv[2]);
random = argc > 3;

if ((rec = malloc(maxnum * sizeof(recType))) == 0) {
fprintf (stderr, "out of memory (rec)\n");
exit(1);
}
if ((key = malloc(maxnum * sizeof(keyType))) == 0) {
fprintf (stderr, "out of memory (key)\n");
exit(1);
}

if ((hashTable = calloc(hashTableSize, sizeof(nodeType *))) == 0) {
fprintf (stderr, "out of memory (hashTable)\n");
exit(1);
}

if (random) { /* random */
/* fill "key" with unique random numbers */
for (i = 0; i < maxnum; i++) key[i] = rand();
printf ("ran ht, %d items, %d hashTable\n", maxnum, hashTableSize);
} else {
for (i=0; i printf ("seq ht, %d items, %d hashTable\n", maxnum, hashTableSize);
}


for (i = 0; i < maxnum; i++) {
err = insert(key[i], &rec[i]);
if (err) printf("pt1, i=%d\n", i);
}

for (i = maxnum-1; i >= 0; i--) {
err = find(key[i], &rec[i]);
if (err) printf("pt2, i=%d\n", i);
}

for (i = maxnum-1; i >= 0; i--) {
err = delete(key[i]);
if (err) printf("pt3, i=%d\n", i);
}
return 0;
}

WAP for External Sorting

/* external sort */

#include
#include
#include

/****************************
* implementation dependent *
****************************/

/* template for workfiles (8.3 format) */
#define FNAME "_sort%03d.dat"
#define LNAME 13

/* comparison operators */
#define compLT(x,y) (x < y)
#define compGT(x,y) (x > y)

/* define the record to be sorted here */
#define LRECL 100
typedef int keyType;
typedef struct recTypeTag {
keyType key; /* sort key for record */
#if LRECL
char data[LRECL-sizeof(keyType)]; /* other fields */
#endif
} recType;

/******************************
* implementation independent *
******************************/

typedef enum {false, true} bool;

typedef struct tmpFileTag {
FILE *fp; /* file pointer */
char name[LNAME]; /* filename */
recType rec; /* last record read */
int dummy; /* number of dummy runs */
bool eof; /* end-of-file flag */
bool eor; /* end-of-run flag */
bool valid; /* true if rec is valid */
int fib; /* ideal fibonacci number */
} tmpFileType;

static tmpFileType **file; /* array of file info for tmp files */
static int nTmpFiles; /* number of tmp files */
static char *ifName; /* input filename */
static char *ofName; /* output filename */

static int level; /* level of runs */
static int nNodes; /* number of nodes for selection tree */

void deleteTmpFiles(void) {
int i;

/* delete merge files and free resources */
if (file) {
for (i = 0; i < nTmpFiles; i++) {
if (file[i]) {
if (file[i]->fp) fclose(file[i]->fp);
if (*file[i]->name) remove(file[i]->name);
free (file[i]);
}
}
free (file);
}
}

void termTmpFiles(int rc) {

/* cleanup files */
remove(ofName);
if (rc == 0) {
int fileT;

/* file[T] contains results */
fileT = nTmpFiles - 1;
fclose(file[fileT]->fp); file[fileT]->fp = NULL;
if (rename(file[fileT]->name, ofName)) {
perror("io1");
deleteTmpFiles();
exit(1);
}
*file[fileT]->name = 0;
}
deleteTmpFiles();
}

void cleanExit(int rc) {

/* cleanup tmp files and exit */
termTmpFiles(rc);
exit(rc);
}

void *safeMalloc(size_t size) {
void *p;

/* safely allocate memory and initialize to zero */
if ((p = calloc(1, size)) == NULL) {
printf("error: malloc failed, size = %d\n", size);
cleanExit(1);
}
return p;
}

void initTmpFiles(void) {
int i;
tmpFileType *fileInfo;

/* initialize merge files */
if (nTmpFiles < 3) nTmpFiles = 3;
file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
for (i = 0; i < nTmpFiles; i++) {
file[i] = fileInfo + i;
sprintf(file[i]->name, FNAME, i);
if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
perror("io2");
cleanExit(1);
}
}
}

recType *readRec(void) {

typedef struct iNodeTag { /* internal node */
struct iNodeTag *parent;/* parent of internal node */
struct eNodeTag *loser; /* external loser */
} iNodeType;

typedef struct eNodeTag { /* external node */
struct iNodeTag *parent;/* parent of external node */
recType rec; /* input record */
int run; /* run number */
bool valid; /* input record is valid */
} eNodeType;

typedef struct nodeTag {
iNodeType i; /* internal node */
eNodeType e; /* external node */
} nodeType;

static nodeType *node; /* array of selection tree nodes */
static eNodeType *win; /* new winner */
static FILE *ifp; /* input file */
static bool eof; /* true if end-of-file, input */
static int maxRun; /* maximum run number */
static int curRun; /* current run number */
iNodeType *p; /* pointer to internal nodes */
static bool lastKeyValid; /* true if lastKey is valid */
static keyType lastKey; /* last key written */

/* read next record using replacement selection */

/* check for first call */
if (node == NULL) {
int i;

if (nNodes < 2) nNodes = 2;
node = safeMalloc(nNodes * sizeof(nodeType));
for (i = 0; i < nNodes; i++) {
node[i].i.loser = &node[i].e;
node[i].i.parent = &node[i/2].i;
node[i].e.parent = &node[(nNodes + i)/2].i;
node[i].e.run = 0;
node[i].e.valid = false;
}
win = &node[0].e;
lastKeyValid = false;

if ((ifp = fopen(ifName, "rb")) == NULL) {
printf("error: file %s, unable to open\n", ifName);
cleanExit(1);
}
}

while (1) {

/* replace previous winner with new record */
if (!eof) {
if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
if ((!lastKeyValid || compLT(win->rec.key, lastKey))
&& (++win->run > maxRun))
maxRun = win->run;
win->valid = true;
} else if (feof(ifp)) {
fclose(ifp);
eof = true;
win->valid = false;
win->run = maxRun + 1;
} else {
perror("io4");
cleanExit(1);
}
} else {
win->valid = false;
win->run = maxRun + 1;
}

/* adjust loser and winner pointers */
p = win->parent;
do {
bool swap;
swap = false;
if (p->loser->run < win->run) {
swap = true;
} else if (p->loser->run == win->run) {
if (p->loser->valid && win->valid) {
if (compLT(p->loser->rec.key, win->rec.key))
swap = true;
} else {
swap = true;
}
}
if (swap) {
/* p should be winner */
eNodeType *t;

t = p->loser;
p->loser = win;
win = t;
}
p = p->parent;
} while (p != &node[0].i);

/* end of run? */
if (win->run != curRun) {
/* win->run = curRun + 1 */
if (win->run > maxRun) {
/* end of output */
free(node);
return NULL;
}
curRun = win->run;
}

/* output top of tree */
if (win->run) {
lastKey = win->rec.key;
lastKeyValid = true;
return &win->rec;
}
}
}

void makeRuns(void) {
recType *win; /* winner */
int fileT; /* last file */
int fileP; /* next to last file */
int j; /* selects file[j] */


/* Make initial runs using replacement selection.
* Runs are written using a Fibonacci distintbution.
*/

/* initialize file structures */
fileT = nTmpFiles - 1;
fileP = fileT - 1;
for (j = 0; j < fileT; j++) {
file[j]->fib = 1;
file[j]->dummy = 1;
}
file[fileT]->fib = 0;
file[fileT]->dummy = 0;

level = 1;
j = 0;


win = readRec();
while (win) {
bool anyrun;

anyrun = false;
for (j = 0; win && j <= fileP; j++) {
bool run;

run = false;
if (file[j]->valid) {
if (!compLT(win->key, file[j]->rec.key)) {
/* append to an existing run */
run = true;
} else if (file[j]->dummy) {
/* start a new run */
file[j]->dummy--;
run = true;
}
} else {
/* first run in file */
file[j]->dummy--;
run = true;
}

if (run) {
anyrun = true;

/* flush run */
while(1) {
if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
perror("io3");
cleanExit(1);
}
file[j]->rec.key = win->key;
file[j]->valid = true;
if ((win = readRec()) == NULL) break;
if (compLT(win->key, file[j]->rec.key)) break;
}
}
}

/* if no room for runs, up a level */
if (!anyrun) {
int t;
level++;
t = file[0]->fib;
for (j = 0; j <= fileP; j++) {
file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
file[j]->fib = t + file[j+1]->fib;
}
}
}
}

void rewindFile(int j) {
/* rewind file[j] and read in first record */
file[j]->eor = false;
file[j]->eof = false;
rewind(file[j]->fp);
if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
if (feof(file[j]->fp)) {
file[j]->eor = true;
file[j]->eof = true;
} else {
perror("io5");
cleanExit(1);
}
}
}

void mergeSort(void) {
int fileT;
int fileP;
int j;
tmpFileType *tfile;

/* polyphase merge sort */

fileT = nTmpFiles - 1;
fileP = fileT - 1;

/* prime the files */
for (j = 0; j < fileT; j++) {
rewindFile(j);
}

/* each pass through loop merges one run */
while (level) {
while(1) {
bool allDummies;
bool anyRuns;

/* scan for runs */
allDummies = true;
anyRuns = false;
for (j = 0; j <= fileP; j++) {
if (!file[j]->dummy) {
allDummies = false;
if (!file[j]->eof) anyRuns = true;
}
}

if (anyRuns) {
int k;
keyType lastKey;

/* merge 1 run file[0]..file[P] --> file[T] */

while(1) {
/* each pass thru loop writes 1 record to file[fileT] */

/* find smallest key */
k = -1;
for (j = 0; j <= fileP; j++) {
if (file[j]->eor) continue;
if (file[j]->dummy) continue;
if (k < 0 ||
(k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
k = j;
}
if (k < 0) break;

/* write record[k] to file[fileT] */
if (fwrite(&file[k]->rec, sizeof(recType), 1,
file[fileT]->fp) != 1) {
perror("io6");
cleanExit(1);
}

/* replace record[k] */
lastKey = file[k]->rec.key;
if (fread(&file[k]->rec, sizeof(recType), 1,
file[k]->fp) == 1) {
/* check for end of run on file[s] */
if (compLT(file[k]->rec.key, lastKey))
file[k]->eor = true;
} else if (feof(file[k]->fp)) {
file[k]->eof = true;
file[k]->eor = true;
} else {
perror("io7");
cleanExit(1);
}
}

/* fixup dummies */
for (j = 0; j <= fileP; j++) {
if (file[j]->dummy) file[j]->dummy--;
if (!file[j]->eof) file[j]->eor = false;
}

} else if (allDummies) {
for (j = 0; j <= fileP; j++)
file[j]->dummy--;
file[fileT]->dummy++;
}

/* end of run */
if (file[fileP]->eof && !file[fileP]->dummy) {
/* completed a fibonocci-level */
level--;
if (!level) {
/* we're done, file[fileT] contains data */
return;
}

/* fileP is exhausted, reopen as new */
fclose(file[fileP]->fp);
if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
== NULL) {
perror("io8");
cleanExit(1);
}
file[fileP]->eof = false;
file[fileP]->eor = false;

rewindFile(fileT);

/* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
tfile = file[fileT];
memmove(file + 1, file, fileT * sizeof(tmpFileType*));
file[0] = tfile;

/* start new runs */
for (j = 0; j <= fileP; j++)
if (!file[j]->eof) file[j]->eor = false;
}
}

}
}


void extSort(void) {
initTmpFiles();
makeRuns();
mergeSort();
termTmpFiles(0);
}

int main(int argc, char *argv[]) {

/* command-line:
*
* ext ifName ofName nTmpFiles nNodes
*
* ext in.dat out.dat 5 2000
* reads in.dat, sorts using 5 files and 2000 nodes, output to out.dat
*/
if (argc != 5) {
printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
cleanExit(1);
}

ifName = argv[1];
ofName = argv[2];
nTmpFiles = atoi(argv[3]);
nNodes = atoi(argv[4]);

printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
nTmpFiles, nNodes, sizeof(recType));

extSort();

return 0;
}

WAP for Rabin Karp String Matching Algorithm

Rabin-Karp Algorithm

Problem Description
Given a string P,T. We want to check whether P is a substring of T.


Algorithm
RabinKarp algorithm performs well in practice and also generalized to other algorithm for related problems, such as two-dimensional pattern matching. The worst case running time is O((n-m+1)*m).

Let's assume that the character used in string T is a set S { 0,1,2,...,9 }. We can view a string of k consecutive character as decimal numbers. For example, string "31415" corresponds to the number 31415.

Given a pattern P[1..m], let p denote its corresponding decimal value. Given a text T[1..n], we let t(s) denote the decimal value of length-m substring T[s+1..s+m] for s = 0,1,...,n-m. Obviously, t(s) = p if and only if T[s+1..s+m] = P[1..m].

We can p compute in O(m) time using Horner's Rule

p = P[m] + 10(P[m-1] + 10(P[m-2] + ... + 10 (P[2] + 10 P[1])...)).

pseudo code for above assumption is

result = 0;
for i = 1 to m
result = result * 10;
result = result + P[i]


We can compute all t(s), for s = 0,1,...,n-m values in a total of O(n) time. The value of t(0) can be similarly computed from T[1..m] in O(m) time. To compute the remaining values t(1), t(2), ..., t (n-m), observe that t(s+1) can be computed can be computed from t(s) in constant time.

t(s+1) = 10*(t(s) - 10^(m-1) * T[s+1]) + T[s + m + 1].

For example,
T = "123456" and m = 3
t(0) = 123
t(1) = 10*(123 - 100*1) + 4 = 234

Step by Step explanation
First : remove the first digit : 123 - 100*1 = 23
Second: Multiply by 10 to shift it : 23 * 10 = 230
Third : Add last digit : 230 + 4 = 234

The algorithm runs by comparing, t(s) with p. When t(s) = p, then we have found the substring P in T, starting from position s.

Generalization
The only problem with above explanation is t(s) and p may be too large, so that no built-in data type can fit them. The solution is we required all t(s) and p be performed in modulo q.

In general, if we have d-ary alphabet { 0,1,...,d-1 }, we could have 26 alphabet { a, b, ..., z }, we choose q so that dq fits within a computer word. We can work out p modulo q by using this pseudo code

result = 0;
for i = 1 to m
result = (d*result + P[i] ) mod q


and computation of t(s+1) become

t(s+1) = d*(t(s) - T[s+1]*h) + T[s + m + 1]) mod q, where h = d^(m-1) (mod q)

The weakness of this method is that, ts = p (mod q) doesn't imply that ts = p. On the other hand, if ts != p (mod q), we definitely know that ts != p. So we can use ts != p (mod q) as a fast heuristic test to rule out invalid shifts s. But if we have ts = p we have have to check whether T[s+1...s+m] = P[1..m]


Implementation in C/C++

/* Rabin-Karp String Matching Algorithm
RabinKarpMatch(T,P,d,q)
- Assume T and P consist only a..z and A..Z
- radix d, prime q
- match whether P is a substring of T
- return the starting index of the first occurence of P in T
- n = length(T)
- m = length(P)

Worst Case : O((n-m+1)*m)
Best Case : O(n+m)
*/

#define tonum(c) (c >= 'A' && c <= 'Z' ? c - 'A' : c - 'a' + 26)

/* return a^p mod m */
int mod(int a,int p,int m)
{
if (p == 0) return 1;
int sqr = mod(a,p/2,m) % m;
sqr = (sqr * sqr) % m;
if (p & 1) return ((a % m) * sqr) % m;
else return sqr;
}

int RabinKarpMatch(char *T,char *P,int d,int q)
{
int i,j,p,t,n,m,h,found;
n = strlen(T);
m = strlen(P);
h = mod(d,m-1,q);
p = t = 0;

for (i=0; i {
p = (d*p + tonum(P[i])) % q;
t = (d*t + tonum(T[i])) % q;
}

for (i=0; i<=n-m; i++)
{
if (p == t)
{
found = 1;
for (j=0; j if (P[j] != T[i+j])
{
found = 0;
break;
}
if (found) return i;
} else {
t = (d*(t - ((tonum(T[i])*h) % q)) + tonum(T[i+m])) % q;
}
}
return -1;
}

WAP Horner Rule

coefficients := [-19, 7, -4, 6] # list coefficients of all x^0..x^n in order
x := 3
accumulator := 0
for i in length(coefficients) downto 1 do
# Assumes 1-based indexing for arrays
accumulator := ( accumulator * x ) + coefficients[i]
done
# accumulator now has the answer



A fast scheme for evaluating a polynomial such as:

-19+7x-4x^2+6x^3,

when

x=3;.

is to arrange the computation as follows:

((((0) x + 6) x + (-4)) x + 7) x + (-19;

And compute the result from the innermost brackets outwards as in this pseudocode:


#include

double horner(double *coeffs, int s, double x)
{
int i;
double res = 0.0;

for(i=s-1; i >= 0; i--)
{
res = res * x + coeffs[i];
}
return res;
}


int main()
{
double coeffs[] = { 3.0, 2.0, 1.0, 1.0 };

printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 2.0));
return 0;
}

TC O(n)
SC O(1)
Run Here https://ideone.com/uGAZC

Write C code to implement the strstr() (search for a substring) function.

This is also one of the most frequently asked interview questions. Its asked almost 99% of the times. Here are a few C programs to implement your own strstr() function.

There are a number of ways to find a string inside another string. Its important to be aware of these algorithms than to memorize them. Some of the fastest algorithms are quite tough to understand!.


Method1

The first method is the classic Brute force method. The Brute Force algorithm checks, at all positions in the text between 0 and (n-m), if an occurrence of the pattern starts at that position or not. Then, after each successfull or unsuccessful attempt, it shifts the pattern exactly one position to the right. The time complexity of this searching phase is O(mn). The expected number of text character comparisons is 2n.

Here 'n' is the size of the string in which the substring of size 'm' is being searched for.

Here is some code (which works!)



#include

void BruteForce(char *x /* pattern */,
int m /* length of the pattern */,
char *y /* actual string being searched */,
int n /* length of this string */)
{
int i, j;
printf("\nstring : [%s]"
"\nlength : [%d]"
"\npattern : [%s]"
"\nlength : [%d]\n\n", y,n,x,m);


/* Searching */
for (j = 0; j <= (n - m); ++j)
{
for (i = 0; i < m && x[i] == y[i + j]; ++i);
if (i >= m) {printf("\nMatch found at\n\n->[%d]\n->[%s]\n",j,y+j);}
}
}


int main()
{
char *string = "hereroheroero";
char *pattern = "hero";

BF(pattern,strlen(pattern),string,strlen(string));
printf("\n\n");
return(0);
}




This is how the comparison happens visually


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
|||| ----> Match!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero







Method2

The second method is called the Rabin-Karp method.

Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string "window" looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used. Hashing a string involves computing a numerical value from the value of its characters using a hash function.

The Rabin-Karp method uses the rule that if two strings are equal, their hash values must also be equal. Note that the converse of this statement is not always true, but a good hash function tries to reduce the number of such hash collisions. Rabin-Karp computes hash value of the pattern, and then goes through the string computing hash values of all of its substrings and checking if the pattern's hash value is equal to the substring hash value, and advancing by 1 character every time. If the two hash values are the same, then the algorithm verifies if the two string really are equal, rather than this being a fluke of the hashing scheme. It uses regular string comparison for this final check. Rabin-Karp is an algorithm of choice for multiple pattern search. If we want to find any of a large number, say k, fixed length patterns in a text, a variant Rabin-Karp that uses a hash table to check whether the hash of a given string belongs to a set of hash values of patterns we are looking for. Other algorithms can search for a single pattern in time order O(n), hence they will search for k patterns in time order O(n*k). The variant Rabin-Karp will still work in time order O(n) in the best and average case because a hash table allows to check whether or not substring hash equals any of the pattern hashes in time order of O(1).

Here is some code (not working though!)


#include

hashing_function()
{
// A hashing function to compute the hash values of the strings.
....
}

void KarpRabinR(char *x, int m, char *y, int n)
{
int hx, hy, i, j;

printf("\nstring : [%s]"
"\nlength : [%d]"
"\npattern : [%s]"
"\nlength : [%d]\n\n", y,n,x,m);


/* Preprocessing phase */
Do preprocessing here..

/* Searching */
j = 0;
while (j <= n-m)
{
if (hx == hy && memcmp(x, y + j, m) == 0)
{
// Hashes match and so do the actual strings!
printf("\nMatch found at : [%d]\n",j);
}

hy = hashing_function(y[j], y[j + m], hy);
++j;
}
}


int main()
{

char *string="hereroheroero";
char *pattern="hero";

KarpRabin(pattern,strlen(pattern),string,strlen(string));

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

}



This is how the comparison happens visually


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
|||| ----> Hash values match, so do the strings!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero





Method3

The Knuth-Morris-Pratt or the Morris-Pratt algorithms are extensions of the basic Brute Force algorithm. They use precomputed data to skip forward not by 1 character, but by as many as possible for the search to succeed.

Here is some code


void preComputeData(char *x, int m, int Next[])
{
int i, j;
i = 0;
j = Next[0] = -1;

while (i < m)
{
while (j > -1 && x[i] != x[j])
j = Next[j];
Next[++i] = ++j;

}
}


void MorrisPrat(char *x, int m, char *y, int n)
{
int i, j, Next[1000];

/* Preprocessing */
preComputeData(x, m, Next);

/* Searching */
i = j = 0;
while (j < n)
{
while (i > -1 && x[i] != y[j])
i = Next[i];
i++;
j++;
if (i >= m)
{
printf("\nMatch found at : [%d]\n",j - i);
i = Next[i];
}
}
}


int main()
{
char *string="hereroheroero";
char *pattern="hero";

MorrisPrat(pattern,strlen(pattern),string,strlen(string));

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



This is how the comparison happens visually


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero



hereroheroero
|||| ----> Match found!
hero


hereroheroero
!
hero




Method4

The Boyer Moore algorithm is the fastest string searching algorithm. Most editors use this algorithm.

It compares the pattern with the actual string from right to left. Most other algorithms compare from left to right. If the character that is compared with the rightmost pattern symbol does not occur in the pattern at all, then the pattern can be shifted by m positions behind this text symbol.


The following example illustrates this situation.

Example:


0 1 2 3 4 5 6 7 8 9 ...
a b b a d a b a c b a
| |
b a b a c |
<------ |
|
b a b a c


The comparison of "d" with "c" at position 4 does not match. "d" does not occur in the pattern. Therefore, the pattern cannot match at any of the positions 0,1,2,3,4, since all corresponding windows contain a "d". The pattern can be shifted to position 5. The best case for the Boyer-Moore algorithm happens if, at each search attempt the first compared character does not occur in the pattern. Then the algorithm requires only O(n/m) comparisons .

Bad character heuristics

This method is called bad character heuristics. It can also be applied if the bad character (the character that causes a mismatch), occurs somewhere else in the pattern. Then the pattern can be shifted so that it is aligned to this text symbol. The next example illustrates this situation.


Example:


0 1 2 3 4 5 6 7 8 9 ...
a b b a b a b a c b a
|
b a b a c
<----
|
b a b a c



Comparison between "b" and "c" causes a mismatch. The character "b" occurs in the pattern at positions 0 and 2. The pattern can be shifted so that the rightmost "b" in the pattern is aligned to "b".


Good suffix heuristics

Sometimes the bad character heuristics fails. In the following situation the comparison between "a" and "b" causes a mismatch. An alignment of the rightmost occurence of the pattern symbol a with the text symbol a would produce a negative shift. Instead, a shift by 1 would be possible. However, in this case it is better to derive the maximum possible shift distance from the structure of the pattern. This method is called good suffix heuristics.

Example:


0 1 2 3 4 5 6 7 8 9 ...
a b a a b a b a c b a
| | |
c a b a b
<----
| | |
c a b a b


The suffix "ab" has matched. The pattern can be shifted until the next occurence of ab in the pattern is aligned to the text symbols ab, i.e. to position 2.


In the following situation the suffix "ab" has matched. There is no other occurence of "ab" in the pattern.Therefore, the pattern can be shifted behind "ab", i.e. to position 5.

Example:


0 1 2 3 4 5 6 7 8 9 ...
a b c a b a b a c b a
| | |
c b a a b
c b a a b



In the following situation the suffix "bab" has matched. There is no other occurence of "bab" in the pattern. But in this case the pattern cannot be shifted to position 5 as before, but only to position 3, since a prefix of the pattern "ab" matches the end of "bab". We refer to this situation as case 2 of the good suffix heuristics.

Example:


0 1 2 3 4 5 6 7 8 9 ...
a a b a b a b a c b a
| | | |
a b b a b
a b b a b



The pattern is shifted by the longest of the two distances that are given by the bad character and the good suffix heuristics.

The Boyer-Moore algorithm uses two different heuristics for determining the maximum possible shift distance in case of a mismatch: the "bad character" and the "good suffix" heuristics. Both heuristics can lead to a shift distance of m. For the bad character heuristics this is the case, if the first comparison causes a mismatch and the corresponding text symbol does not occur in the pattern at all. For the good suffix heuristics this is the case, if only the first comparison was a match, but that symbol does not occur elsewhere in the pattern.


More Resources

http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node41.html
http://www.cs.aau.dk/~simas/aalg04/slides/aalg3.ppt
http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm

WAP for Prime No..Checking & Generation in any range say n

bool is_prime(int x)
{
if(x <= 1)
return false;
for(int i = 2; i < x; i++)
if(x%i == 0)
return false;
return true;
}

This will however will loop through all elements below x to see if a factor exists. Example, for finding if 13 is prime, we check if its divisible by 2,3,4,....12. This can be optimized to loop through only half the elements since the highest factor is going to be num/2 as,


bool is_prime(int x)
{
if(x <= 1)
return false;
for(int i = 2; i <= x/2; i++)
if(x%i == 0)
return false;
return true;
}

But by analysis you can see that for a number say 100, the factors are (1*100),(2*50),(4*25),(5*20),(10*10),(20*5),(25*4),(50*2),(100*1). For finding out if 100 is prime or not we just need to check if 100 is divisible by any number not greater than 10 i.e., it is sufficient to check from 2 to 10. The reason being if its divisible by 4, its also divisible by 25.

Hence the best approach to check if a number is prime or not will be


bool is_prime(int x)
{
if(x <= 1)
return false;
int s = (int) sqrt(x);
for(int i = 2; i <= s; i++)
if(x%i == 0)
return false;
return true;
}


Generate Prime Number in A Range

/* Generate a prime list from 0 up to n, using The Sieve of Erantosthenes
param n The upper bound of the prime list (including n)
param prime[] An array of truth value whether a number is prime
*/
void prime_sieve(int n, bool prime[]) {
prime[0] = false;
prime[1] = false;
int i;
for (i = 2; i <= n; i++)
prime[i] = true;

int limit = sqrt(n);
for (i = 2; i <= limit; i++) {
if (prime[i]) {
for (int j = i * i; j <= n; j += i)
prime[j] = false;
}
}
}

Java Program //Working


public class prime_sieve
{


public static void main(String a[])
{

runEratosthenesSieve(100);

}

public static void runEratosthenesSieve(int upperBound) {

int upperBoundSquareRoot = (int) Math.sqrt(upperBound);

boolean[] isComposite = new boolean[upperBound + 1];

for (int m = 2; m <= upperBoundSquareRoot; m++) {

if (!isComposite[m]) {

System.out.print(m + " ");

for (int k = m * m; k <= upperBound; k += m)

isComposite[k] = true;

}

}

for (int m = upperBoundSquareRoot; m <= upperBound; m++)

if (!isComposite[m])

System.out.print(m + " ");

}


}

Populating next right pointers in each node (Sibling)

struct Node {
Node* leftChild;
Node* rightChild;
Node* nextRight;
}

Populate the nextRight pointers in each node.
You may assume that it is a full binary tree (ie, each node other than the leaves has two children.)

Naive Algorithm:-
1. Most likely this can be implemented recursively, because you can identify the linking of nodes as sub-problems.
2. The main difficulty of this problem is linking rightChild with the nextSibling of rightChild.
3. Each node has no parent pointer. Therefore, there is no way linking the rightChild with its nextSibling at a level.

as its naive you will find exactness of some more test cases covered in below working code .

Pseudo Code :-

void connect(Node* p)
{
if (!p) return;
if (p->leftChild)
p->leftChild->nextRight = p->rightChild;
if (p->rightChild)
p->rightChild->nextRight = (p->nextRight) ?
p->nextRight->leftChild :
NULL;
connect(p->leftChild);
connect(p->rightChild);
}



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

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node* left;
    struct node* right;
    struct node* nextRight;

};

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  node->nextRight=NULL;
  return(node);
}

void connect(struct node* p) {
  if (!p)
  return;
 
  if (p->left)
  {
    if(p->right)//its necessary else NULL Pointer Exception
          p->left->nextRight = p->right;

    else if(p->nextRight)
    {
        if(p->nextRight->left)/// we can add one more if(p->nextRight)
          p->left->nextRight=p->nextRight->left;
        else if(p->nextRight->right)
          p->left->nextRight=p->nextRight->right;
    }  
    else
         p->left->nextRight=NULL;//if all are null except that node at that level
  }

  if (p->right)
  {
    if(p->nextRight)
    {
        if(p->nextRight->left)//skipping checking the root null or not
            p->right->nextRight =p->nextRight->left;
        else if(p->nextRight->right)//skipping checking the root null or not
            p->right->nextRight =p->nextRight->right;
    }
    else
             p->right->nextRight=NULL;
  }
  connect(p->left);
  connect(p->right);
}

/* Driver program to test above functions*/
int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right  = newNode(5);
  root->right->left= newNode(6);
  root->right->right= newNode(7);
  root->left->left->left  = newNode(8);
  root->left->left->right  = newNode(9);
  root->left->right->left  = newNode(10);
  root->left->right->right  = newNode(11);
  root->right->left->left= newNode(12);
  root->right->left->right= newNode(13);
  root->right->right->left= newNode(14);
  root->right->right->right= newNode(15);



  connect(root);
 
  printf( " %d %d %d ", root->left->left->nextRight->data,root->left->right->nextRight->data,root->right->left->nextRight->data);
  printf(" %d %d %d ",root->left->left->left->nextRight->data,root->left->left->right->nextRight->data,root->right->right->left->nextRight->data);//,root->right->right->right->nextRight->data); it will be null


  getchar();
  return 0;
}

Time Complexity O(N^2)
Space Complexity O(1)
Run Here https://ideone.com/lTPuY


2nd Method Using Queue
Just modified the structure of node of tree
struct tree{ int val; tree* left; tree* right; tree* rpeer; };
‘rpeer’ will have the address of next node of same level. For last node at any level, rpeer will be NULL.

At the beginning, all the rpeer nodes are assigned NULL. Write a program to populate correct value in rpeer for whole tree.

Example:
Input tree:Output tree: horizontal arrows are showing rpeer for every node.
Answer: As we are seeing that rpeer is next element at the same level. So if we are able to fetch the next element at same level, we are done. As per our prior knowledge, we can access these element using breadth first traversal.

Now only problem is how to check if we are at last element at any level. For this reason, we should be appending a delimiter (NULL in this case) to mark end of a level.

Efficient Algorithm:

Put root in queue.Put NULL in queue.While Queue is not emptyx = fetch first element from queueIf x is not NULL x->rpeer <= top element of queue. put left and right child of x in queueelse if queue is not empty put NULL in queueend ifend whilereturn
Code:

Algo is Correct Code Modification Needed :P  BDW Enjoy its Great Spoon Feeding :)

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


/* A binary tree node has data, pointer to left child
and a pointer to right child */
typedef struct node
{
int data;
struct node* left;
struct node* right;
struct node* nextRight;

}node;

typedef node * Tree;

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
node* node = (node*)malloc(sizeof(node));
node->data = data;
node->left = NULL;
node->right = NULL;
node->nextRight=NULL;

return(node);
}


void connect(Tree root)
{
std::list que; //Queue to store tree nodes
que.push_back(root);
que.push_back(NULL); //null is the delimeter to show end of the level

if (!root)
return;

Tree *l, *r;

while(!que.empty())
{
Tree *tmp= que.front();
que.pop_front();

if(tmp != NULL)
{
tmp->nextRight= que.front();
l = tmp->left;
r = tmp->right;
if(l) que.push_back(l);
if(r) que.push_back(r);
}
else
{
if (!que.empty())
que.push_back(NULL);
}
}
return;
}

int main()
{
Tree root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left= newNode(6);
root->right->right= newNode(7);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
root->left->right->left = newNode(10);
root->left->right->right = newNode(11);
root->right->left->left= newNode(12);
root->right->left->right= newNode(13);
root->right->right->left= newNode(14);
root->right->right->right= newNode(15);



connect(root);

printf( " %d %d %d ", root->left->left->nextRight->data,root->left->right->nextRight->data,root->right->left->nextRight->data);
printf(" %d %d %d ",root->left->left->left->nextRight->data,root->left->left->right->nextRight->data,root->right->right->left->nextRight->data);//,root->right->right->right->nextRight->data); it will be null


getchar();
return 0;
}

Time Complexity O(N^2)
Run Here  https://ideone.com/8Kgnb
Space Complexity O(1)
R

WAP Print Edge Nodes (Boundary) of a Binary Tree

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.

Variant: Print the same for a tree that is not complete.


______30______
/ \
__20__ __40__
/ \ / \
10 25 35 50
/ \ \ /
5 15 28 41


o/p 30, 20, 10, 5, 15, 28, 35, 41, 50, 40.




50 17 12 9 14 19 67 76 72

similerly for this tree


/* program to check if a tree is height-balanced or not */
#include
#include
#define bool int

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}


void printLeftEdges(node *p, int print) {
if (!p) return;
if (print || (!p->left && !p->right))
printf(" %d",p->data);
printLeftEdges(p->left, print);
printLeftEdges(p->right, (print && !p->left ? 1: 0));
}

void printRightEdges(node *p, int print) {
if (!p) return;
printRightEdges(p->left, (print && !p->right ? 1: 0));
printRightEdges(p->right, print);
if (print || (!p->left && !p->right))
printf(" %d", p->data);
}

void printOuterEdges(node *root) {
if (!root) return;
printf(" %d ", root->data);
printLeftEdges(root->left, 1);
printRightEdges(root->right, 1);
}

int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->left = newNode(8);
root->right->left=newNode(6);
root->right->right=newNode(7);
root->right->left->left=newNode(9);
root->right->right->right=newNode(10);

printOuterEdges(root);

getchar();
return 0;
}


2nd Method

its Awesome & Cool Solution

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */

enum {LEFT, RIGHT, LEAF};


struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}



int isleaf(struct node* tree)
{
return (!(tree->left || tree->right));
}

void rperipheral (struct node* root, int state)
{
if(root)
{
switch (state)
{
case LEFT:
printf("\t %d", root->data);
rperipheral(root->left, LEFT);
rperipheral(root->right, LEAF);
break;
case RIGHT:
rperipheral(root->left, LEAF);
rperipheral(root->right, RIGHT);
printf("\t %d", root->data);
break;
case LEAF:
if (isleaf(root))
printf("\t %d", root->data);
rperipheral(root->left, LEAF);
rperipheral(root->right, LEAF);
break;
}
}
}

void peripheral (struct node* root)
{
printf("%d",root->data);
rperipheral(root->left, LEFT);
rperipheral(root->right, RIGHT);
}



int main()
{
struct node *root = newNode(0);
root->left = newNode(1);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(4);
root->left->left->left = newNode(5);
root->left->right->right = newNode(6);
root->left->right->left = newNode(7);
root->left->right->right = newNode(8);
root->right->left = newNode(13);
root->right->right = newNode(14);
root->right->left->left = newNode(9);
root->right->left->right = newNode(10);
root->right->right->left = newNode(11);
root->right->right->right = newNode(12);

peripheral(root);


return 0;

}

Time Complexity O(N)
Space Complexity O(1)
Run here https://ideone.com/MUb3L