Create a Doubly Linked List from a Ternary Tree in C++

In this tutorial, we are going to learn how to create a doubly linked list from a ternary tree in C++. Here we will learn about the ternary tree, doubly linked list, and how to create a doubly linked list from a ternary tree. After that we will see the C++ program for the same.

Ternary Tree

A ternary tree is a data structure in which each node has at most three children.
Ternary means composed of three parts. So, in a ternary tree, the parent node can have at most three child nodes, which are often called as the ‘left’, ‘middle’, and ‘right’ node, respectively. The structure of a node is defined as:-

struct node{  
    int val;  
    struct node *left;  
    struct node *middle;  
    struct node *right;  
};

Here, the variables ‘left’ points to the left subtree, ‘middle’ points to the middle subtree, and ‘right’ points to the right subtree. The variable ‘val’ stores the value or data of a node. Let us see an example:-

1
/     |     \
/         |         \
2            6         10
/  |  \       /  |  \       /  |  \
  3   4   5     7  8  9    11  12  13

Doubly Linked List

A doubly-linked list is a data structure that contains sequentially linked records i.e. nodes. It is a variation of a singly linked list. In the doubly linked list we can move or traverse in both the direction forward as well as backward. The structure of a node is defined as:-

struct node { 
    int val; 
    struct node* next;
    struct node* prev;
};

Here, the variable ‘next’ points to the next node, and the variable ‘prev’ points to the previous node. The variable ‘val’ stores the value or data of a node. Let us see an example:-

null<–>1<–>2<–>3<–>4<–>5<–>6<–>7<–>8<–>9<–>10<–>11<–>12<–>13<–>null

Algorithm to create a doubly linked list from a ternary tree

We can create a doubly linked list from the ternary tree by using any of the following traversal:-

• Using pre-order traversal.
• Using in-order traversal.
• Or, using post-order traversal.

Here, we will create a doubly-linked list from the given ternary tree by storing the pre-order traversal of the given ternary tree. So, here are the steps to create a doubly linked list from a ternary tree:-

1. Create a ternary tree with any number of nodes.
2. Create an empty doubly-linked list with head and tail pointers.
3. Perform the pre-order traversal of the ternary tree.
4. While performing the pre-order traversal, append the current node in the doubly-linked list simultaneously.
5. At last, our doubly linked list is created from a ternary tree and it contains the pre-order traversal of the ternary tree.

C++ program to create a doubly linked list from ternary tree

So, here is the C++ implementation of the above algorithm:-

#include<bits/stdc++.h>
using namespace std;
//Structure of a node of the ternary tree  
  
struct TreeNode
{  
    int val;  
    TreeNode *left;  
    TreeNode *middle;  
    TreeNode *right;  
};        
  
TreeNode *head=NULL, *tail = NULL;  


/*=====================================================
FUNCTION TO CONVERT TERNARY TREE TO DOUBLY LINKED LIST
=======================================================*/
void create_doubly_from_ternary(TreeNode *root) 
{  
    // Check node is null or not.If it is null then return 
    if(!root)                        
        return;  
      
    //storing the address of left child  
    TreeNode *left_subtree = root->left;  
    //storing the address of middle child        
    TreeNode *middle_subtree = root->middle;
    //storing the address of right child
    TreeNode *right_subtree = root->right;       
      
    if(head == NULL)             // If list is empty 
    {   
        // Make head and tail equal to root;
        head = tail = root;        
        //And store null in root->middle,head->left 
        //& tail->right                      
        root->middle = head->left = tail->right = NULL;  
    }  

    //If list is not empty
    else {    
        //insert new node after tail                  
        tail->right = root;    
        //And store tail address in root->left to maintain 
        //doubly linked list property
        root->left = tail;     
        root->middle = NULL;   
        //root will become new tail 
        tail = root;         
        //And tail->right should be null
        tail->right = NULL;  
    }  
    
    //Recursively call left subtree
    create_doubly_from_ternary(left_subtree);     
    //Recursively call middle subtree
    create_doubly_from_ternary(middle_subtree);   
    //Recursively call right subtree
    create_doubly_from_ternary(right_subtree);    
}  


   
/*============================================
FUNCTION TO DISPLAY THE DOUBLY LINKED LIST
=============================================*/
void display_doubly_linked_list() 
{   
    TreeNode *ptr = head;  
    if(head == NULL)       //Checking for empty list
    {  
        cout<<"Your list is empty"<<endl; 
        return;  
    }
    cout<<"New converted doubly linked list is:"<<endl<<endl;
    cout<<"null";
    while(ptr != NULL)    //Terminate when ptr==NULL
    {  
        cout<<" <-> "<<ptr->val;
        ptr = ptr->right;   //Increment ptr to right
    }  
    cout<<" <-> null"<<endl;
}  


/*===========================================
FUNCTION TO CREATE NEW NODE FOR TERNARY TREE
============================================*/
TreeNode* makeTreeNode(int data)
{                                               
    TreeNode *newTreeNode = new TreeNode();      
    newTreeNode->val = data;                     
    return newTreeNode;  
} 


/*======================================
   MAIN FUNCTION
=======================================*/
int main()  
{  
    TreeNode *root;          
    //Make a ternary tree by calling 
    //function makeTreeNode()  
    root = makeTreeNode(1);  
    root->left = makeTreeNode(2);  
    root->left->left = makeTreeNode(3);  
    root->left->middle = makeTreeNode(4);  
    root->left->right = makeTreeNode(5);  
    root->middle = makeTreeNode(6);  
    root->middle->left = makeTreeNode(7);  
    root->middle->middle = makeTreeNode(8);  
    root->middle->right = makeTreeNode(9);  
    root->right = makeTreeNode(10);  
    root->right->left = makeTreeNode(11);  
    root->right->middle = makeTreeNode(12);  
    root->right->right = makeTreeNode(13);  
    
    //Representation of input tree
    //                  1
    //            /     |     \
    //        /         |         \
    //       2          6         10
    //    /  |  \    /  |  \    /  |  \
    //   3   4   5  7   8  9   11  12  13
      
    //Calling converting function that create doubly 
    //linked list from ternary tree  
    create_doubly_from_ternary(root);  
      
    //Calling display function to print final 
    //converted doubly linked list
    display_doubly_linked_list();      
   
    return 0;  
}

Output:-

New converted doubly linked list is:

null <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 <-> 9 <-> 10 <-> 11 <-> 12 <-> 13 <-> null

Thanks for reading this tutorial. I hope it helps you !!