Data Structures & Algorithm

Algorithm to Convert BST to DDL (Recursive Traversal of BST)
public static int nodes = 0;
public static DDListNode listHead;
   public DDListNode TreeToList(OrderNode root) {
     if (root != null) {
         TreeToList(root->left);
if (nodes==0) listHead = null;
listHead = sortedInsert(listHead, root->data,root->deliveryPriority,root->datePlaced);
TreeToList(root->right);
}
return listHead;
}

public DDListNode sortedInsert(DDListNode listHead, int data,int p,int d){
DDListNode listnode = new DDListNode(data,p,d);
if (listHead==null){ (no nodes in LL)
nodes++;
return listnode;
}
else{
if (listHead->next==null){ ( only one node in LL )
if (listnode->deliveryPriority > listHead->deliveryPriority){
listHead->next = listnode;
listnode->prev = listHead;
return listHead;
}
else if (listnode->deliveryPriority < listHead->deliveryPriority){
listHead->prev = listnode;
listHead->next = null;
listnode->next = listHead;
return listnode;
}
else { ( equal priorities)
if(listnode->datePlaced < listHead->datePlaced){
listHead->prev = listnode;
listHead->next = null;
listnode->next = listHead;
return listnode;
}
else if(listnode->datePlaced > listHead->datePlaced){
listHead->next = listnode;
return listHead;
}
else{
listHead->next = listnode;
return listHead;
}
}
}
else { // listHead->right has nodes
// traverse through the nodes
DDListNode cur = listHead;
DDListNode prev = cur->prev;

if (listnode->deliveryPriority > cur->deliveryPriority){
while(cur!=null){
prev = cur;
cur = cur->next;
if (listnode->deliveryPriority > cur->deliveryPriority){
continue;
}
else if (listnode->deliveryPriority < cur->deliveryPriority){
listnode->prev = cur->prev;
prev->next = listnode;
listnode->next = cur;
cur->prev = listnode;
return listHead;
}
else { // =
if(listnode->datePlaced < cur->datePlaced){
listnode->prev = cur->prev;
prev->next = listnode;
listnode->next = cur;
cur->prev = listnode;
return listHead;
}
else if(listnode->datePlaced > cur->datePlaced){
if (cur->next!=null){
if(cur->next->deliveryPriority > listnode->deliveryPriority){
listnode->prev = cur;
cur->next = listnode;
return listHead;
}
}
else if (cur->next==null){
listnode->prev = cur;
cur->next = listnode;
return listHead;
}
else
continue;
}
else{ // datePlaceds equal
listnode->next = cur->next;
listnode->prev = cur;
cur->next = listnode;
return listHead;
}
}
}

cur->next = listnode;
listnode->prev = cur;
return listHead;
}
else if (listnode->deliveryPriority < cur->deliveryPriority){
cur->prev = listnode;
listnode->next = cur;
return listnode;
}
else { (priorities are equal)
if(listnode->datePlaced < cur->datePlaced){
cur->prev = listnode;
listnode->next = cur;
return listnode;
}
else if(listnode->datePlaced > cur->datePlaced){
cur->next = listnode;
return cur;
}
else{
cur->next = listnode;
return cur;
}
}
}
}
}
Algorithm to Convert BST to DDL (Iterative Traversal of BST)
    public DDListNode TreeToList(OrderNode root) {
DDListNode listHead = null;
        if(root == null)
            return null;

        Stack<OrderNode> s = new Stack<OrderNode>();
        OrderNode curNode = root;

        while(!s->empty() || curNode!=null){

            if(curNode!=null)
            {
                s->push(curNode);
                curNode=curNode->left;
            }
            else
            {
                OrderNode node = s->pop();

listHead = sortedInsert(listHead, node->data,node->deliveryPriority,node->datePlaced);
                curNode=node->right;
            }
}
return listHead;
    }

public DDListNode sortedInsert(DDListNode listHead, int data,int p,int d){
DDListNode listnode = new DDListNode(data,p,d);
if (listHead==null){ (no nodes in LL)
return listnode;
}
else{
if (listHead->next==null){ ( only one node in LL )
if (listnode->deliveryPriority > listHead->deliveryPriority){
listHead->next = listnode;
listnode->prev = listHead;
return listHead;
}
else if (listnode->deliveryPriority < listHead->deliveryPriority){
listHead->prev = listnode;
listHead->next = null;
listnode->next = listHead;
return listnode;
}
else { ( equal priorities)
if(listnode->datePlaced < listHead->datePlaced){
listHead->prev = listnode;
listHead->next = null;
listnode->next = listHead;
return listnode;
}
else if(listnode->datePlaced > listHead->datePlaced){
listHead->next = listnode;
return listHead;
}
else{
listHead->next = listnode;
return listHead;
}
}
}
else { // listHead->right has nodes
// traverse through the nodes
DDListNode cur = listHead;
DDListNode prev = cur->prev;

if (listnode->deliveryPriority > cur->deliveryPriority){
while(cur!=null){
prev = cur;
cur = cur->next;
if (listnode->deliveryPriority > cur->deliveryPriority){
continue;
}
else if (listnode->deliveryPriority < cur->deliveryPriority){
listnode->prev = cur->prev;
prev->next = listnode;
listnode->next = cur;
cur->prev = listnode;
return listHead;
}
else { // =
if(listnode->datePlaced < cur->datePlaced){
listnode->prev = cur->prev;
prev->next = listnode;
listnode->next = cur;
cur->prev = listnode;
return listHead;
}
else if(listnode->datePlaced > cur->datePlaced){
if (cur->next!=null){
if(cur->next->deliveryPriority > listnode->deliveryPriority){
listnode->prev = cur;
cur->next = listnode;
return listHead;
}
}
else if (cur->next==null){
listnode->prev = cur;
cur->next = listnode;
return listHead;
}
else
continue;
}
else{ // datePlaceds equal
listnode->next = cur->next;
listnode->prev = cur;
cur->next = listnode;
return listHead;
}
}
}

cur->next = listnode;
listnode->prev = cur;
return listHead;
}
else if (listnode->deliveryPriority < cur->deliveryPriority){
cur->prev = listnode;
listnode->next = cur;
return listnode;
}
else { (priorities are equal)
if(listnode->datePlaced < cur->datePlaced){
cur->prev = listnode;
listnode->next = cur;
return listnode;
}
else if(listnode->datePlaced > cur->datePlaced){
cur->next = listnode;
return cur;
}
else{
cur->next = listnode;
return cur;
}
}
}
}
}