CareerCup

I think the following code should work

node* inorderconvert(node *T, node *lastprinted) {
    if(T->left != NULL)
        lastprinted = inorderconvert(T->left, lastprinted);
    if lastprinted == NULL
        Head = T;
    else {
        lastprinted->right = T;
        T->left = lastprinted;
        lastprinted = T;
    }
    if(T->right != NULL)
        lastprinted = inorderconvert(T->right, lastprinted);
    return lastprinted;
}

call the function with

tail = inorderconvert(root, NULL);

Here is the solution:
Tree* Convert(Tree *T)
{
Tree *l1,*l2;
if(T!=NULL)
{
l1=Convert(T->left);
l2=Convert(T->right);
if(l1!=NULL)
l1->right=T;
T->left=l1;
T->right=l2;
if(l2!=Null)
{
l2-left=T;
return l2;
}
else
return T;
}
}

I am assuming we will use the left pointer to point to back node and right pointer to point to forward node.

the following code works:



node * Tree :: convLnLst(node *T){
node *l1,*l2;
node * temp;

if(T!=NULL){
l1=convLnLst(T->left);
l2=convLnLst(T->right);

T->left=l1;
T->right=l2;


if(l2!=NULL){
l2->left=T;
}

if(l1!=NULL){
temp=l1;
while(temp->right)
temp=temp->right;
temp->right=T;
l1->left=NULL;
return l1;
}
else
return T;

}
else
return NULL;

}

Hi Ravi ,Why have u added this loop
while(temp->right)
temp=temp->right;
temp->right=T;
l1->left=NULL;
Just asking as when I uploaded the algo I didn't implement it, just thought the possible solution.

the above algo posted by me takes O(n*n) time

the following algo takes O(n) time

call this fuction with flag = -1


node * Tree :: convLnLst(node *T,int flag){
node *l1,*l2;

if(T!=NULL){
l1=convLnLst(T->left,0);
l2=convLnLst(T->right,1);

T->left=l1;
T->right=l2;

if(l1!=NULL){
l1->right=T;
}

if(l2!=NULL){
l2->left=T;
}
if(flag==0 && T->right)
return T->right;

if(flag==1 && T->left)
return T->left;

if(flag==-1){
while(T->left)
T=T->left;
}

return T;
}
return NULL;
}

//This 1 'll work i guess

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

typedef struct node* nodeptr;

main()
{
nodeptr root=NULL;

//populate the tree

change(root);

//traversing back to the beginning of list by using left node of root
//will take us to head of the doubly linked list.

}

void change(nodeptr temp)
{
nodeptr nextNode;
if(temp->left && temp->right)//if the root has both childs
{
nextNode = temp->left;//store the left child as it is needed to link to its parent
change(temp->left);
nextNode->right = temp;

nextNode = temp->right;
//store the right child as it is needed to link to its parent
change(temp->right);
nextNode->left = temp;
}
else if(temp->left && !temp->right)//onli left child is present
{
nextNode = temp->left;
change(temp->left);
nextNode->right = temp;
}
else if(!temp->left && temp->right) //onli right child is present
{
nextNode = temp->right;
change(temp->right);
nextNode->left = temp;
}
}

Hey naveen

when will the recursive call to change() end ?? there is no termination condition??

Proper working code is here:
#include <stdio.h>
#include<stdlib.h>
typedef struct node1{
int val;
struct node1* left;
struct node1 *right;
}tree;
tree* insert(tree *root,int val);
tree ** convert(tree *root);
void print(tree *root);
void printL(tree *root);
int main(){
int n,temp,i;
tree *root=NULL;
list *head=NULL;
list *tail=NULL;
printf("Enter the no of nodes");
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&temp);
if(root==NULL)
root=insert(root,temp);
else insert(root,temp);
}
printf("ans \n\n");
print(root);
tree ** temp1 = convert(root);
printL(temp1[0]);
getch();
return 0;
}
void printL(tree *head){
while(head!=NULL){
printf("%d",head->val);
head=head->right;
}
}
tree ** convert(tree *root){
tree ** ret,**left,**right;
left = NULL;
right=NULL;
tree *temp = (tree *)malloc(sizeof(list));
temp->val=root->val;
ret = (tree **)malloc(2);
if(root->left!=NULL)left=convert(root->left);
if(root->right!=NULL)right=convert(root->right);
if(left!=NULL){
temp->left=left[1];
left[1]->right=temp;
left[0]->left=NULL;
ret[0]= left[0];
}
if(right!=NULL){
temp->right=right[0];
right[0]->left=temp;
right[1]->right=NULL;
ret[1]=right[1];
}
if(left==NULL){
temp->left=NULL;
ret[0]=temp;
}
if(right==NULL){
temp->right=NULL;
ret[1]=temp;
}
return ret;
}
void print(tree *root){
if(root==NULL)return;
if(root!=NULL){
print(root->left);
printf("%d",root->val);
print(root->right);
}
}
tree* insert(tree *root,int val){
if(root ==NULL){
tree *temp = (tree *)malloc(sizeof(tree));
temp->val=val;
temp->right=NULL;
temp->left=NULL;
root=temp;
return root;
}
if(root->val>val && root->left == NULL){
tree *temp = (tree *)malloc(sizeof(tree));
temp->val=val;
temp->right=NULL;
temp->left=NULL;
root->left=temp;
return root;
}
if(root->val<val && root->right == NULL){
tree *temp = (tree *)malloc(sizeof(tree));
temp->val=val;
temp->right=NULL;
temp->left=NULL;
root->right=temp;
return root;
}
if(val<root->val)insert(root->left,val);
else insert(root->right,val);
}

assume for double link list
left->backward
right ->forward

BS *convert(BS *root){
if(!root)return root;
if(!root->left && !root->right) return root;

BS *left=convert(root->left);
BS *right=convert(root->right);
if(left){
left->right=root;
if(right)right->left=root;
return left;
}
else{
if(right)right->left=root;
return root;

}
}

same as
thecareerplus.com/forum/viewtopic.php?p=414#414

This works

TNode* head = Tree.ConvertToDList(tree.root,false);

static TNode* Tree::ConvertToDList(TNode* root, bool IsLeft)
{
if( NULL == root)
return NULL;

TNode* left = ConvertToDList(root->left, true);
TNode* right = ConvertToDList(root->right, false);

root->left = left;
root->right = right;

if(left)
left->right = root;
if(right)
right->left = root;

if(IsLeft)
{
while(root->right)
root = root->right;
}
else
{
while(root->left)
root = root->left;
}

return root;
}

I think Inorder traversing would suffice.

Tested to be working.

Node* BST2List(Node* bst)
{
	Node* first = NULL;
	static Node* last = NULL;
	
	if (bst == NULL) return NULL;

	if (bst->left == NULL) first = bst;
	else first = BST2List(bst->left);

	if (last != NULL) last->right = bst;
	bst->left = last;
	last = bst;

	if (bst->right != NULL) bst->right = BST2List(bst->right);

	return first;
}

this line is not necessary: else bst->right = NULL;

Thanks

hghg

node * convertDouble (node *root,node **prev )
{
static node * first = NULL;

if(!root) return NULL;
if(root->left==NULL && first == NULL) first = root ;

convertDouble(root->left,prev);
root->left=*prev;
if(*prev) (*prev)->right = root;
*prev=root;
convertDouble(root->right,prev);

return first;

}

How about this?

void convert_to_dll(tree_node *node, tree_node **head, tree_node **tail) {

tree_node *temp_l_tail = node;
tree_node *temp_r_head = node;

if(node == NULL)
return;

if(node->left != NULL) {
convert_to_dll(node->left, head, &temp_l_tail);
temp_l_tail->right = node;
node->left = temp_l_tail;
} else {
*head = node;
}

if(node->right != NULL) {
convert_to_dll(node->right, &temp_r_head, tail);
temp_r_head->left = node;
node->right = temp_r_head;
}else {
*tail = node;
}

}

struct node
{
int data;
struct node * lptr;
struct node * rptr;
struct node * link;
}

struct node * sort_tree(struct node * root)
{
struct node * previous = NULL;
struct node * start_link = NULL;
sorted_link(root,&previous,&start_link);
return(start_link);
}

struct node * sorted_link (struct node * root, struct node ** previous, struct node ** start_link)
{
if(root == NULL || previous == NULL || start_link == NULL) return NULL;

if(root->lptr != NULL) sorted_link(root->lptr,previous,start_link);
if(*previous != NULL)
{
(*previous->link) = root;
}
else *start_link = root;
*previous = root;
root->link = NULL;
if(root->rptr != NULL) sorted_link(root->rptr,previous,start_link);
}

This is for singly linked list, which could be easily extended for doubly linked list... have fun ;-)

for a doubly linked list ... i guess this algo will work fine..

If we do inorder traversal for a tree T
say call to inorder traversal return a node NODE each time (i mean one by one so that we can easily modify that NODE)

while((NODE=InorderTraversal(tree T))!=NULL)
{
NODE->right=Successor(NODE);
NODE->left=Predeccesor(NODE);
}
The code for finding a successor and predecessor is very well given in alorithm book by Prof Cormen.
This Algo only changes the pointers(left and right) without using any temporary variable..and also it does not modify the pointer value unless required...

tree * head, *curr

convert_to_dll(tree *t)
{
if(!t)return;
convert_to_dll(t->left);
curr->right=t;
t->left=curr;
curr=t;
convert_to_dll(t->right);
}

int main()
{
head=malloc(sizeof(tree));
curr=head;
convert_to_dll(root);
curr->right=head;
head->left=curr;
return 0;
}

I am not very sure about the below solution, please give your comments.
this is simply to convert the BST to Singly link list. We can easily create a doubly link list from a singlt link list.

Node inOrder(Node n){
if(n->left==null)
return n;
else
inOrder(n->left)->right = n;

if(n->right==null) return n;
else
n->right= inOrder(n->right);

}