How to convert a binary search tree into a doubly

Question

Given a binary search tree, i need to convert it into a doubly linked list(by traversing in zig zag order) using only pointers to structures in C++ as follows,

Given Tree:

                1
                |
        +-------+---------+
        |                 |
        2                 3
        |                 |
   +----+---+        +----+---+
   |        |        |        |
   4        5        6        7
   |        |        |        |
+--+--+  +--+--+  +--+--+  +--+--+
|     |  |     |  |     |  |     |
8     9  10    11 12    13 14    15

Node Structure:

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

Create List(zig zag order):

1 <-> 3 <-> 2 <-> 4 <-> 5 <-> 6 <-> 7 <-> 15 <-> ... <-> 8

Could someone please help me out.

Answer 1

/* * File: main.cpp * Author: viswesn * * Created on December 1, 2010, 4:01 PM */

struct node {

int item; 
struct node *left; 
struct node *right; 
    struct node *next; 
    struct node *prev; 
};

struct node *dlist = NULL;

struct node *R = NULL;

struct node* EQueue[10] = {'\0'};

int Etop = 0;

struct node* OQueue[10] = {'\0'};

int Otop = 0;

int level=-1;

struct node *insert(struct node *R, int item)

{

struct node *temp = NULL; 

if (R != NULL) { 
    if (item < R->item) { 
        R->left = insert(R->left, item); 
    } else { 
        R->right = insert(R->right, item); 
    } 
} else { 
    temp = (struct node *)malloc(sizeof(struct node)); 
    if (temp == NULL) { 
        return NULL; 
    } 
    temp->item = item; 
    temp->left = NULL; 
    temp->right = NULL; 
            temp->next = NULL; 
            temp->prev = NULL; 
    R = temp; 
} 
return R; 
}

void print(struct node *node)

{

if (node != NULL) { 

    print(node->left); 
    printf("%d<->", node->item); 
    print(node->right); 
} 
}

void EvenEnqueue(struct node *item) {

if (Etop > 10) { 
    printf("Issue in EvenEnqueue\n"); 
    return; 
} 
EQueue[Etop] = item; 
Etop++; 
}

void OddEnqueue(struct node *item)

{

if (Otop > 10){ 
    printf("Issue in OddEnqueue\n"); 
    return; 
} 
OQueue[Otop] = item; 
Otop++; 
}

int isEvenQueueEmpty() {

if (EQueue[0] == '\0') { 
    return 1; 
} 
return 0; 
}

int isOddQueueEmpty()

{

if (OQueue[0] == '\0') { 
    return 1; 
} 
return 0; 
}

void EvenDQueue()

{

int i = 0; 
for(i=0; i< Etop; i++) 
    EQueue[i]='\0'; 
Etop = 0; 
}

void OddDQueue()

{

int i = 0; 
for(i=0; i< Otop; i++) 
    OQueue[i]='\0'; 
Otop = 0; 
}

void addList() {

int counter = 0; 
struct node *item = NULL; 
if (level%2 == 0) { 
        /* Its Even level*/ 
        while(counter < Etop) 
        { 
            struct node *t1 = EQueue[counter]; 
            struct node *t2 = EQueue[counter+1]; 
            if ((t1!=NULL) && (t2!=NULL)) { 
                t1->next = t2; 
                t2->prev = t1; 
            } 
            counter++; 
        } 
        item = EQueue[0]; 
} else { 
        /* Its odd level */ 
        while(counter < Otop) 
        { 
            struct node *t1 = OQueue[counter]; 
            struct node *t2 = OQueue[counter+1]; 
            if ((t1!=NULL) && (t2!=NULL)) { 
                t2->next = t1; 
                t1->prev = t2; 
            } 
            counter++; 
        } 
         item = OQueue[Otop-1]; 
} 

if(dlist !=NULL) { 
    dlist->next = item; 
} 
item->prev = dlist; 
if (level%2 == 0) { 
    dlist = EQueue[Etop-1]; 
} else { 
    dlist = OQueue[0]; 
} 
}

void printTree()

{

int nodeCount = 0; 
int counter = 0; 

if (!isEvenQueueEmpty()) { 
    /* If even level queue is not empty */ 
    level++; 
    nodeCount = pow(2,level); 
            printf("["); 
    while(counter < nodeCount) { 
        if (EQueue[counter] != '\0') { 
            struct node *t = EQueue[counter];                                
            printf("%d<->", t->item); 
                            if (t->left != NULL) 
                                OddEnqueue(t->left); 
                            if (t->right != NULL) 
                                OddEnqueue(t->right);                
        } else { 
                        break; 
                    } 
        counter++; 
    } 
            addList(); 
            printf("]"); 
            EvenDQueue(); 
} 
counter = 0; 
if (!isOddQueueEmpty()){ 
            /* If odd level queue is not empty */ 
    level++; 
    nodeCount = pow(2,level); 
            printf("["); 
    while(counter < nodeCount){ 
        if (OQueue[counter] != '\0') { 
            struct node *t = OQueue[counter];                                 
            printf("%d<->", t->item); 
                            if (t->left != NULL) 
                                EvenEnqueue(t->left); 
                            if (t->right != NULL) 
                                EvenEnqueue(t->right); 
        } else { 
                        break; 
                    } 
        counter++; 
    } 
            addList(); 
            printf("]"); 
            OddDQueue(); 
} 
if (isEvenQueueEmpty() && isOddQueueEmpty()){ 
    return; 
} 
else { 
    printTree(); 
} 
}

void printLevel(struct node *node)

{

if (node == NULL) 
    return; 
EvenEnqueue(node); 
printTree(); 
    printf("\n"); 
}

void printList(struct node *item)

{

while(item!=NULL) { 
    printf("%d->", item->item); 
    item = item->next; 
} 
}

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

int a[]={20,30,40,12,2,15,18}; 
int size = sizeof(a)/sizeof(int); 
int i = 0; 

for(i=0; i< size; i++) { 
    R = insert(R, a[i]); 
} 
    printf("Inoder traversal - Binary tree\n"); 
print(R); 
printf("\n\n"); 
    printf("Level traversal - Binary tree\n"); 
printLevel(R); 
    printf("\n"); 
    printf("Double link list traversal - Binary tree\n"); 
    printList(R); 
    printf("\n"); 
return 0; 
}

Answer 2

This is a Breadth-first search algorithm. Wikipedia has a good explanation on how to implement it.

After implementing the algorithm, creating your linked list should be a no-brainer (since it will only be a matter of appending each visited element to the list)

Answer 3

#include<iostream>
#include<conio.h>
using namespace std;

class TreeNode
{
public:
    int info;
    TreeNode* right;
    TreeNode* left;
    //TreeNode* parent;
    TreeNode()
    {
        info = 0;
        right = left = NULL;
    }

    TreeNode(int info)
    {
        this -> info = info;
        right = left = NULL;
    }
};

class ListNode
{
public:
    int info;
    ListNode* next;
    ListNode()
    {
        info = 0;
        next = NULL;
    }

    ListNode(int info)
    {
        this -> info = info;
        next = NULL;
    }
};

TreeNode* root = NULL;
ListNode* start;
ListNode* end;

void addTreeNode(TreeNode*);
void convertTreeToList(TreeNode*);
void printList(ListNode*);
int findDepth(TreeNode*);

int _tmain(int argc, _TCHAR* argv[])
{
    start = end = new ListNode(0);
    char choice = 'y';
    int info;
    while(choice == 'y')
    {
        cout<<"Enter the info of new node:\n";
        cin>>info;
        addTreeNode(new TreeNode(info));
        cout<<"Want to add a new node to the tree?(y/n)\n";
        cin>>choice;
    }

    cout<<"Depth of the tree is: "<<findDepth(root);

    cout<<"Converting the tree into a doubly linked list....\n";

    convertTreeToList(root);
    printList(start->next);
    cin>>choice;
    return 0;
}



void addTreeNode(TreeNode* node)
 {
     if(!root)
     {
         root = node;
     }
     else
     {
         TreeNode* currRoot = root;
         while(1)
         {
             if(node -> info >= currRoot -> info)
             {
                 if(!currRoot -> right)
                 {
                     currRoot -> right = node;
                     break;
                 }
                 else
                 {
                     currRoot = currRoot -> right;
                 }
             }
             else
             {
                 if(!currRoot -> left)
                 {
                     currRoot -> left = node;
                     break;
                 }
                 else
                 {
                     currRoot = currRoot -> left;
                 }
             }
         }
     }
 }

 void convertTreeToList(TreeNode* node)
 {
     if(node -> left != NULL)
     {
         convertTreeToList(node -> left);
     }

         end ->next = new ListNode(node -> info);
         end = end -> next;
         end -> next = start;



         if(node -> right != NULL)
     {
         convertTreeToList(node -> right);
     }

 }


 void printList(ListNode* start)
 {
     while(start != ::start)
     {
         cout<<start->info<<" -> ";
         start = start -> next;
     }
     cout<<"x";
 }

 int findDepth(TreeNode* node)
 {
     if(!node)
     {
         return 0;
     }
     else
     {
         return (max(findDepth(node -> left), findDepth(node -> right)) + 1);
     }
 }

Linked list you get here is singly linked and sorted. Hope you can easily make changes in this code to get a doubly linked list. Just copy - paste this code and compile it.It will work fine.

Answer 4

you can write a function to add nodes in a doubly linked list. You can then call this function while traversing the tree. In this way you should be able to do it.

Answer 5

This ( http://cslibrary.stanford.edu/109/TreeListRecursion.html) has the answer with pretty pictures :)

Answer 6

This might help you:

2. Create a separate list for every level of the tree
3. Traverse the tree and copy the values to the lists as you traverse the tree
4. Reverse the order of every other list
5. Connect the lists