Sunday, 23 December 2012

Tree to Double Linked List without extra space


Problem : To convert a BST to a sorted Double Linked List.

#include<iostream.h>
#include<stdio.h>

//Using same node struct for Tree and List.

class Node{
public:
int data;
Node* left;
Node* right;
};

Node *head=NULL;
Node* lastNode =NULL;

void createList(Node *temp)
{
if(head==NULL)
{
head=temp;
lastNode=head;
}
else
{

lastNode->right = temp;
temp->left=lastNode;
lastNode = temp;
}
}


void print(Node* node)
{
if(node)
{
print(node->left);
cout<<" node data : "<<node->data <<endl;
print(node->right);
}
};


void inorder(Node* node)
{
if(node)
{
inorder(node->left);
createList(node);
inorder(node->right);
}
};

Node* create(int data,Node *node)
{
if(node==NULL)
{
cout<<"Adding first node "<<endl;
node=new Node();
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
if(node->data>=data)
{
cout<<"Adding to the left"<<endl;
node->left=create(data,node->left);

}
else
{
cout<<"Adding to the right"<<endl;
node->right=create(data,node->right);
}
return node;
}

void main()
{
int data;
Node *temp=NULL;
char b='a';
while(b!='k')
{
cout<<"enter data"<<endl;
cin>>data;
temp=create(data,temp);
cout<<"enter choice"<<endl;
cin>>b;
}

print(temp);

cout<<"converitng to double linked list by calling tree inorder"<<endl;
inorder(temp);

Node* t=head;
while(t)
{
cout<<"Data :"<<t->data<<endl;
t=t->right;
}

cout<<"printing from end"<<endl;

t=lastNode;
while(t)
{
cout<<"Data :"<<t->data<<endl;
t=t->left;
}

}

No comments:

Post a Comment

AWS Data Pipeline Services

https://www.youtube.com/watch?v=tykcCf-Zz1M