May 032017
 

The structure of Node of a Binary Tree and Doubly linked list are same.

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

 Structure of Node of a Binary Tree    

struct Node
{
   int data;
   Node* previous;
   Node* next; 
}

  Structure of Node of a Doubly linked list

If we treat left pointer as previous and right pointer as next, we can use the Node of a Binary Tree to represent node of a Doubly linked list or vice-versa.

Given a binary tree, modify the pointers in each node of the tree so that they represent a Doubly linked. Order of the nodes in DLL should be same as that in the in-order traversal.

If the Input Binary tree is as below

Binary Search Tree

then the function should modify pointers in the nodes, as shown below and return the head pointer.

Doubly Linked List
Continue reading »

Oct 252016
 

Write a recursive function that add 5 to the alternate nodes of the linked list. For example, if the list is

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

then the function should change the list to the below one

1 -> 7 -> 3 -> 9 -> 5 -> 11 -> 7 -> 13 -> 9 -> 15

Iterative Solution:

The code to add 5 to alternate nodes is straight forward. We will just skip the alternate nodes. Below is the iterative solution for the same: Continue reading »

Feb 182016
 

In C language, string library has a function strcmp that takes two arguments and return -1, 0 or 1 depending on whether first string is less than equal-to or greater than the second string.

 
int strcmp(const char *str1, const char *str2);

Write similar function that compare strings given in the form of linked list, For example:

If:
  First List:  s->a->n->s->k->r->i->t
  Second List: s->a->n->s->k->r->i->t->i
Output: -1

If:
  First List:  s->a->n->s->k->r->i->t
  Second List: a->t->m->a->n
Output: 1

If:
  First List:  n->o->n->t->r->a->n->s->l->a->t->a->b->l->e
  Second List:  n->o->n->t->r->a->n->s->l->a->t->a->b->l->e
Output: 0

The signature of function will change like as shown below:

 
int strcmp(Node *head1, Node *head2);

Continue reading »